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

860. 柠檬水找零

leetcode
文档题解
视频题解

没什么特殊技巧，仅凭直觉，上来就是模拟，唯一和贪心相关的可能就是优先找面值最大的。

看到 Carl 是这么解释贪心的：账单是 20 的情况，为什么要优先消耗一个 10 和一个 5 呢？因为美元 10 只能给账单 20 找零，而美元 5 可以给账单 10 和账单 20 找零，美元5更万能！

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int[] money = new int[3];
        for (int bill : bills) {
            if (bill == 5) {
                money[0]++;
            } else if (bill == 10) {
                money[1]++;
                // 要找 5 块钱
                if (money[0] == 0) {
                    return false;
                } else {
                    money[0]--;
                }
            } else if (bill == 20) {
                money[2]++;
                // 找 15 块钱
                int x = 15;
                // 优先找 10 块
                while (x >= 10 && money[1] > 0) {
                    money[1]--;
                    x -= 10;
                }
                while (x >= 5 && money[0] > 0) {
                    money[0]--;
                    x -= 5;
                }
                if (x != 0) return false;
            }
        }
        return true;
    }
}

406. 根据身高重建队列

leetcode
文档题解
视频题解

重点关注 k 属性，因为要求的队列的顺序是按照 k 表示的意思排序的，k 表示的意思是前面有 k 个人的身高大于等于 h。所以要先将 h 按照从大到小的顺序（为什么？还是看 k 的意思，前面的人高）安定下来，再根据 k 去考虑这个人的位置。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 先按身高降序排序，如果身高相等，就按 k 的升序排列
        Arrays.sort(people, (int[] a, int[] b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return b[0] - a[0];
            }
        });
        LinkedList<int[]> list = new LinkedList<>();
        // 再按 k 插入到列表中
        for (int[] person : people) {
            int idx = person[1];
            list.add(idx, person);
        }
        // 将结果转为二维数组
        int[][] res = new int[list.size()][];
        int i = 0;
        for (int[] e: list) {
            res[i++] = e;
        }
        return res;
    }
}

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

leetcode
文档题解
视频题解

一开始没看懂 XY 平面是什么意思，直接在一条直线上画图看相交的部分，相交的多了就很杂乱。后来看了题解才发现是一个平面直角坐标系，相交的部分看起来就清晰多了，也更容易想出解题思路。

从图中可以发现，如果当前气球的左边界小于上一个气球的右边界，那么是可以用一只箭射爆的，然后更新右边界，用于判断下一个气球是否也在这个范围内。否则就得多用一只箭。

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        // 注意这里的减法，可能会溢出，参考用例 [[-2147483646,-2147483645],[2147483646,2147483647]]
        // Arrays.sort(points, (int[] a, int[] b) -> a[0] - b[0]);
        // 改为 Integer.compare，可以按左边界排序，下面就正向循环，也可以按右边界排序，下面就反向循环
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        // 记录右边界
        int prevEnd = points[0][1];
        int arrowCount = 1;

        for (int i = 1; i < points.length; i++) {
            int[] curr = points[i];
            if (curr[0] > prevEnd) {
                // 不相交
                arrowCount++;
                prevEnd = curr[1];
            } else {
                // 取较小值更新右边界，想要尽纳容纳更多的气球，就要看短板
                prevEnd = Math.min(prevEnd, curr[1]);
            }
        }

        return arrowCount;
    }
}