LeetCode刷题日记之贪心算法（四）

前言

在前几篇文章中，我们已经覆盖了贪心算法的基本思路和多种题型。这次我将继续分享几道具有挑战性的贪心题目。希望这篇文章能为大家带来更多解题灵感和技巧

柠檬水找零

LeetCode题目链接

这道题就是能否给顾客正确找零，你的柠檬水摊位卖5美元但你一开始没有零钱，一个整数数组bills,其中每个元素是指第i顾客付的帐，这里注意顾客给的不是5块10块就是20块

我们来思路梳理

• 我们贪心策略就是优先使用大额的零钱进行找零。如果需要找 15 美元，应该优先使用 10 美元加 5 美元的组合，这样可以保留更多的 5 美元零钱，以备后续使用

• 我们进一步来梳理这里的找零情况，可以维护两个变量， 一个记录 5 美元的数量，一个记录 10 美元的数量。

  • 如果顾客支付 5 美元，不需要找零，直接增加 5 美元的数量
  • 如果顾客支付 10 美元，需要找 5 美元的零，检查是否有足够的 5 美元。如果没有，则返回 false
  • 如果顾客支付 20 美元，需要找 15 美元，优先使用 10 美元加 5 美元的组合进行找零，如果没有 10 美元，则需要使用三张 5 美元进行找零。如果也不能找零，返回 false

逻辑梳理的很清楚了，完整贪心代码如下

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0; //记录手头5美元的数量
        int ten = 0; //记录手头10美元的数量

        for(int bill : bills){
            if(bill == 5){//顾客支付5美元
                five++;
            }
            else if(bill == 10){//顾客支付10美元
                if(five > 0){
                    five--;
                    ten++;
                }else{
                    return false;
                }
            }else{ //顾客支付20元
                //优先使用一张10美元和两张5美元
                if(ten > 0 && five > 0){
                    ten--;
                    five--;
                }else if(five >= 3){
                    five -= 3;
                }else{
                    return false;
                }
            }
        }

        return true;
    }
}

这道题重点还是找钱逻辑要梳理清楚

根据身高重建队列

LeetCode题目链接

这道题就是说有一群人站成一排，但是它们的顺序不对，一个二维数组，其中每个数组[h,k]其中h是这个人的身高，k是他应该站的位置，含义是指这个人前面有k个身高大于他的人

我们来思路梳理

• 首先按照每个人的身高 h 从高到低排序。如果身高相同，则按照 k（前面有多少个大于等于他的人）从小到大排序。这是因为身高高的人不会受到比他矮的人的影响，身高矮的人则需要依据前面更高的人的数量进行插入
• 按照排好序的数组依次插入队列。每个人的 k 值表示在最终队列中他应该插入的位置，即他前面有 k 个比他身高高的人。由于数组是从高到低排列的，后续的插入不会影响已经插入的高个子
• 贪心策略采用优先按照k值处理高个子，这样当身高矮的人插入时，前面已经有了更高的个子，这样保证插入时不影响已插入的高个子

逻辑梳理完毕，完整代码如下

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //排序
        Arrays.sort(people, (a, b) -> {
            if(a[0] == b[0]){ 
                return a[1] - b[1];//按k值从小到大排序
            }else{
                return b[0] - a[0];//按身高从高到低排序
            }
        });

        //用列表插入元素
        List<int[]> queue = new LinkedList<>();
        for(int[] person : people){
            queue.add(person[1], person);//按照k值插入位置
        }

        return queue.toArray(new int[people.length][2]);
    }
}

可能不好理解的部分

• Arrays.sort()方法通过比较器Comparator来实现升降序逻辑
  • 当 Comparator 返回负数时，a 被认为比 b “小”，a 被排在 b 前面
  • 当 Comparator 返回正数时，a 被认为比 b “大”，a 被排在 b 后面

这说明Comparator就是默认进行升序排列的，a-b < 0说明a比b小则Comparator会把a排列在前面，反之说明a比b大则会把a放在后面,所以只要把a[1]-b[1]则默认升序k值，反过来b[0]-a[0]则表示降序身高

• queue.add(index, element),其中index为要插入的位置，element为要插入的元素，当在指定的 index 位置插入一个新元素时，该位置的现有元素以及所有后续元素都会向后移动一位，为新元素腾出位置，该方法十分契合题目重新排序的逻辑

用最少数量的箭引爆气球

LeetCode题目链接

这道题的表述看起来非常的复杂，但实际上就是一个区间重合的问题，就是若干个气球的位置[start, end],然后求最小弓箭数量，弓箭的x如果大于start小于end则就能引爆气球

我们来思路梳理

• 我们需要将气球按照它们的结束坐标（end）进行升序排序。这样做的原因是：如果一支箭可以射中尽可能多的气球，那么它应该射在尽量靠近当前一批气球结束的位置（即最小的 xend 位置）。这可以确保当前射出的箭能够覆盖更多的气球。所以贪心选择在当前气球的结束坐标 xend 处射出一支箭，这样可以保证尽可能多的气球被引爆。当遇到下一个气球的起始坐标 xstart 大于当前箭的射击位置时，意味着需要再射出一支箭。当当前气球无法被已有的箭射中时，更新箭的位置并增加箭的数量

逻辑梳理的很清晰，完整代码如下

class Solution {
    public int findMinArrowShots(int[][] points) {
        //按照气球结束位置升序排序
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;//初始化箭矢的数量
        int arrowPos = points[0][1];//初始化当前箭的射出位置

        for(int i = 1; i < points.length; i++){
            if(points[i][0] > arrowPos){//如果当前气球的起始位置大于箭的位置，说明需要新的箭
                arrows++;
                arrowPos = points[i][1];//更新箭的位置为当前气球的结束位置
            }
        }
        return arrows;
    }
}

这里有个点和上题排序处理不一样的是Integer.compare(a[1], b[1])不会产生整数溢出问题，这话怎么说呢，如下图所示，如果采用return a[1]-b[1]的方式，当处理很大的整数时，两数相减的结果可能会超出整数范围致使报错

总结

通过这几道题目，我们可以看到贪心算法在解决区间、排序、和找零等问题时的强大之处。贪心算法的核心在于每一步都做出局部最优解，从而推导出全局最优解。在解题过程中，贪心策略的选择至关重要，要仔细分析每步局部选择的可行性，并确保这种局部选择能够带来全局最优，希望博主记录的内容能够给大家带来帮助