代码随想录算法训练营-贪心算法-4|406. 根据身高重建队列、452. 用最少数量的箭引爆气球

406. 根据身高重建队列

1. 一定要想如何确定一个维度，然后再按照另一个维度重新排列。

2. 先确定身高的维度，降序排列。

3. 按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

4. 局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性。

5. 全局最优：最后都做完插入操作，整个队列满足题目队列属性。

6. 插入的过程：

• 插入[7,0]：[[7,0]]
• 插入[7,1]：[[7,0],[7,1]]
• 插入[6,1]：[[7,0],[6,1],[7,1]]
• 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
• 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

• 时间复杂度：O(nlog n + n^2)
• 空间复杂度：O(n)

# -x[0]表示降序,x[1]表示升序

 1 class Solution:
 2     def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
 3         # 先按照h维度的身高顺序从高到低排序。确定第一个维度
 4         # lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序
 5         people.sort(key=lambda x: (-x[0], x[1]))
 6         que = []
 7     
 8     # 根据每个元素的第二个维度k，贪心算法，进行插入
 9         # people已经排序过了：同一高度时k值小的排前面。
10         for p in people:
11             que.insert(p[1], p)
12         return que

452. 用最少数量的箭引爆气球

局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

• 时间复杂度：O(nlog n)，因为有一个快排。
• 空间复杂度：O(1)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间。

 1 class Solution:
 2     def findMinArrowShots(self, points: List[List[int]]) -> int:
 3         if len(points) == 0: return 0
 4         points.sort(key=lambda x: x[0])
 5         result = 1
 6         for i in range(1, len(points)):
 7             if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=
 8                 result += 1     
 9             else:
10                 points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界
11         return result