代码随想录｜Day29｜贪心04｜860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球

860.柠檬水找零

我们维护三种金额的数量：five，ten，twenty

有如下三种情况：

• 账单是5：five + 1，无需找零
• 账单是10：ten + 1，找零一张5元（five - 1）
• 账单是20：twenty + 1，找零一张10元一张5元（ten - 1, five -1），或找零三张5元（five -3）

前两种情况都是固定策略，第三种情况存在两种策略。

如果账单是20，应该优先消耗一个10元一个5元，而不是三个5元。为什么？

因为10元只能用来给20元账单找零，而5元既可以给20元或10元账单找零。

5元更万能，因此使用贪心策略，优先消耗10元，可以给更多的账单找零。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten, twenty = 0, 0, 0
        
        for bill in bills:
            # 5元账单
            if bill == 5:
                five += 1
            # 10元账单
            elif bill == 10:
                ten += 1
                if five > 0:
                    five -= 1
                else:
                    return False
            # 20元账单
            elif bill == 20:
                twenty += 1
                # 优先使用10元找零
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

406.根据身高重建队列

如果同时考虑两个属性 h 和 k，那么很容易顾此失彼。

我们首先考虑身高属性 h，由于 k 描述的是前面有 k 个身高大于或等于 h 的人，因此更高的应该排在前面，我们按照身高 h 降序排序数组。对于身高相同的人，按照 k 升序排序。

接着考虑属性 k，我们将 k 当作索引，重新安排排序后的数组即可得到结果。举个例子，[5, 1]，意味着此人之前有 1个 身高 不矮于5 的人，由于先前已经按照身高排序，因此此人应该被安插在 第二个 位置。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 排序
        # -x[0]：按照身高h降序排序
        # x[1]：如果身高h相同，按照人数k降序排列
        people.sort(key = lambda x: (-x[0], x[1]))
        res = []
        # 重建
        for p in people:
            # 以 k 为索引重建队列
            res.insert(p[1], p)
        return res

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

思路：按照左边界对数组进行排序，通过判断当前气球的左边界 是否大于 上一个气球的右边界来判断是否重叠。需要注意的是，存在2个甚至更多气球重叠的情况，因此每次发现重叠气球的情况时，我们需要寻找一个最优的射击位置：重叠气球中最小的右边界。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 按左边界排序
        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][1], points[i][1])
        return result