算法训练Day35 贪心算法专题 | LeetCode860. 柠檬水找零（没有思路就先模拟过程）；406. 根据身高重建队列(不能两头兼顾）；452. 用最少数量的箭引爆气球（重叠区间）_贪心法柠檬水找零

前言：

算法训练系列是做《代码随想录》一刷，个人的学习笔记和详细的解题思路，总共会有60篇博客来记录，计划用60天的时间刷完。 

内容包括了面试常见的10类题目，分别是：数组，链表，哈希表，字符串，栈与队列，二叉树，回溯算法，贪心算法，动态规划，单调栈。

博客记录结构上分为 思路，代码实现，复杂度分析，思考和收获，四个方面。

如果这个系列的博客可以帮助到读者，就是我最大的开心啦，一起LeetCode一起进步呀；）
 

目录

LeetCode860. 柠檬水找零 

1. 思路

2. 代码实现

3. 代码实现

4. 思考与收获

LeetCode406. 根据身高重建队列

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

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

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

---

LeetCode860. 柠檬水找零 

链接：860. 柠檬水找零 - 力扣（LeetCode）

1. 思路

这道题目刚一看，可能会有点懵，这要怎么找零才能保证完整全部账单的找零呢？但仔细一琢磨就会发现，可供我们做判断的空间非常少！

只需要维护三种金额的数量，5，10和20；有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

此时大家就发现 情况一，情况二，都是固定策略，都不用我们来做分析了，而唯一不确定的其实在情况三。

而情况三逻辑也不复杂甚至感觉纯模拟就可以了，其实情况三这里是有贪心的；账单是20的情况，为什么要优先消耗一个10和一个5呢？因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

• 所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
• 局部最优可以推出全局最优，并找不出反例，那么就试试贪心算法！

2. 代码实现

# 贪心算法
# time:O(N);space:O(1)
class Solution(object):
    def lemonadeChange(self, bills):
        """
        :type bills: List[int]
        :rtype: bool
        """
        five = 0
        ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five<=0: return False 
                else: 
                    five -= 1
                    ten += 1
 
            else:
                if five>0 and ten>0:
                    five -= 1
                    ten -= 1
                elif five>=3:
                    five -=3
                else: return False
        return True

3. 代码实现

• 时间复杂度：O（N）

  其中N为数组bills的长度，需要从头到尾遍历一遍数组；

• 空间复杂度O(1）

  只用了常数个变量来储存元素；

4. 思考与收获

1. 本题咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定；这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂了。

Reference：代码随想录 (programmercarl.com)

本题学习时间：30分钟。

---

LeetCode406. 根据身高重建队列

链接：406. 根据身高重