代码随想录算法训练营第三十六天|860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球

860.柠檬水找零

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

注意看提示：

• bills[i] 不是 5 就是 10 或是 20

 场景较为固定

遇到了20，优先消耗10

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        total = {5:0,10:0,20:0}
        for i in bills:
            if i == 5:
                total[5] += 1 
            elif i == 10:
                
                if total[5] <= 0 : #小于等于
                    return False
                
                total[5] -= 1
                total[10] += 1 
            else:
                #三张5块或者一张10块，一张5块
                #优先找10块的，因为5块更通用
                if total[5] > 0 and total[10]>0:
                    
                    total[5] -= 1
                    total[10] -= 1
                    total[20] += 1
               
                elif total[5] >=3:
                    
                    total[5] -= 3
                    total[20] += 1
                else:
                    return False
                
        print(total)
        return True

406.根据身高重建队列

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

遇到了两个维度都需要考虑的时候，一定不要同时去考虑，要确定一个维度之后，再确定另一个维度，这样思路才清晰

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

key=lambda x: (-x[0], x[1]): 这是sort方法的关键参数，它指定了排序的规则。在这里，使用了一个匿名函数（lambda函数）作为key，它接受一个参数x，表示列表中的每个元素。这个函数返回一个元组，元组的第一个元素是-x[0]，表示以列表中每个元素的第一个元素的相反数作为排序的依据，第二个元素是x[1]，表示以列表中每个元素的第二个元素作为次要排序的依据。

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

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

个人简单思路： 主要是看两个区间之间有没有交点，如何判断有没有交点，有交点的就可以用一支箭射出，没有的就保存下来，用两只箭射出

 局部最优：让重叠的气球尽量在一起，用一支弓箭去射，全局最优：用了最少的弓箭数

不需要射爆一个气球就将这个气球从数组中移除，只需要记录弓箭数即可  

对气球进行排序，统一按照左边界，重叠的气球相邻了

有如下情况：

①如果i气球的左边界大于i-1气球的右边界，那么就一定不重合了，添加弓箭

②如果i气球的左边界小于等于i-1气球的右边界，那么就一定重合了，不需要添加弓箭

判断两个气球重叠之后，还要判断与第三个气球是否重叠，这时候，需要更新右边界

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0 :
            return 0
        points.sort(key = lambda x:x[0])
        result = 1
        for i in range(1,len(points)):
            #左大于右
            if (points[i][0] > points[i-1][1]):
                result += 1
            else:
                #有重叠要更新右边界,重复的气球的右边界的最小值
                points[i][1] = min(points[i][1],points[i-1][1])
        return result

要点（误区）：①对于数组中的气球，是否射一个就要把这个元素移除②如何判断两个气球重叠或是不重叠（排序） ③两个气球重叠后，如何判断和下一个气球也重叠（更新右边界）