贪心算法总结归类（图文解析）

贪心算法实际上并没有什么套路可言，贪心的关键就在于它的思想：

如何求出局部最优解，通过局部最优解从而推导出全局最优解

常见的贪心算法题目

455. 分发饼干

这题的解法很符合“贪心”二字

如果使用暴力的解法，那么本题是通过不了的

那怎么使用求得局部最优从而推导出全局最优呢？

注意：题意中提到了这么一句话

如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足

假如说每次分给孩子的饼干都是刚好满足这个条件，也就是说让尽可能大的饼干喂给胃口大的孩子，从而喂饱每一个孩子，就能达到全局最优：尽可能满足越多数量的孩子

所以本题的代码应该这么写：

让s和g排好序后，都选择从后向前遍历两个数组，从而实现尽可能大的饼干喂给胃口大的孩子，从而喂饱每一个孩子

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);        
        Arrays.sort(s);
        
        int result = 0;
        int index = s.length - 1;
        
        for(int i = g.length - 1;i >= 0;i--){
            if(index > 0 && s[index] >= g[i]){//注意要写上index > 0防止空指针异常（这里是为了避免饼干没了但是还有小孩没遍历到的情况）
                result++;
                index--;
            }
        }
        return result;
    }

1005. K 次取反后最大化的数组和

这题就很简单了，直接上思想：使用局部最优推出全局最优

局部最优：使用while循环，每次循环找出最小的数字并将它的符号进行转换（负数变成正数/正数变成负数）

全局最优：返回数组的最大和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        while(k-- > 0){
            int min = Integer.MAX_VALUE;
            int index = 0;
            for(int i = 0;i < nums.length;i++){
                if(nums[i] < min){
                    min = nums[i];
                    index = i;
                }
            }
            nums[index] = -nums[index];
        }

        int ans = 0;
        
        for(int i :nums){
            ans += i;
        }

        return ans;
    }
}

860. 柠檬水找零

这题的难度和上一题相同，直接上思想使用局部最优推出全局最优

局部最优：遇到账单20，优先消耗美元10，完成本次找零

全局最优：完成找零工作

    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        int twenty = 0;
        for(int i = 0;i < bills.length;i++){
            if(bills[i] == 5){
                ++five;
            }
            if(bills[i] == 10){
                if(five != 0){
                    --five;
                    ++ten;
                }else{
                    return false;
                }
            }
            if(bills[i] == 20){
                if(five >= 3 && ten == 0){
                    five -= 3;
                    ++twenty;
                }else if(five != 0 && ten != 0){
                    --five;
                    --ten;
                    ++twenty;
                }else{
                    return false;
                }
            }
        }
        return true;
    }

376. 摆动序列

根据题目的意思

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

本题我们使用的是贪心算法，局部最优：寻找局部的差值波动 全局最优的到最长的摆动序列

以题目提供的例子

nums = [1,7,4,9,2,5] 各元素之间的差值为 (6, -3, 5, -7, 3)

所以有 6 个摆动序列

nums = [1,2,3,4,5,6,7,8,9] 各元素之间的差值为 (1,1,......,1)

所以有2个摆动序列

根据这两个例子我们可以画一个图来进行解释

先来解释第二个例子 这个例子其实就是对应了如何处理数组左边或者右边的情况

题目中给出的结果是如果只有两个元素，那么就算2个摆动序列

如果我们直接写死了处理数组左边或者右边的情况直接是2个摆动序列

但我们这里不写死，进行判断操作，根据题意我们至少需要三个数字才能确定这个数字是不是摆动序列，那么我们可以理解成[1,9] == [1,1,9]，前面的差值为0 后面的差值为9 此时就有了差值波动

而我们初始result = 1 那么此时出现了 差值波动 所以 result++ 后就有了2个摆动序列

然后我们再来解释第一个例子

由于需要判断前后的差值 所以此时我们设置两个变量 prediff 记录前面差值 curdiff 记录当前差值

结合第二个例子

以 1 7 4 为例子 prediff = 6 而 curdiff = -3

所以 prediff >= 0 && curdiff <= 0 所以此时算一个摆动序列

以 7 4 9 为例子 prediff = -3 而 curdiff = 5

所以 prediff <= 0 && curdiff >= 0 所以此时算一个摆动序列

 所以我们写出代码

    public int wiggleMaxLength(int[] nums) {
        int prediff = 0;
        int curdiff = 0;
        int result = 1;

        for(int i = 0;i < nums.length-1;i++){
            curdiff = nums[i+1] - nums[i];
            if(prediff >= 0 && curdiff < 0 || prediff <= 0 && curdiff > 0){
                result++;
            }
            prediff = curdiff;    
        }

        return result;
    }

但其实这里的代码是有一点问题的，我们的 prediff = curdiff; 实际上要放到if里面进行判断

为什么？我这里再举一个例子

假如说我们的单调递增有平坡，由于prediff是实时更新的，所以在 1 9 9 这个区间内会被计算成一个摆动序列 但是我们的题目中要求 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 所以此时不能算一个摆动序列

为了解决这个问题，我们直接让curdiff不再实时更新

而是当出现差值波动时 prediff 更新成当前的差值即可

最终代码如下

    public int wiggleMaxLength(int[] nums) {
        int prediff = 0;
        int curdiff = 0;
        int result = 1;

        for(int i = 0;i < nums.length-1;i++){
            curdiff = nums[i+1] - nums[i];
            if(prediff >= 0 && curdiff < 0 || prediff <= 0 && curdiff > 0){
                result++;
                prediff = curdiff;
            }
        }

        return result;
    }

738. 单调递增的数字

 题目描述：

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

本题的解题思路：使用贪心算法

局部最优：每当相邻的两个数字 x > y 时将y后的所有数字变成9同时让x-1

全局最优：返回 小于或等于 n 的最大数字，且数字呈 单调递增 

以332为例子

首先将数字转换成字符串，然后再将字符串转换成数组方便我们进行操作 

根据题意我们选择从后向前遍历，当我们发现x > y时使用一个变量来记录 y的下标

        for(int i = charNum.length - 1;i >= 1;i--){
            if(i > 0 && charNum[i] < charNum[i-1]){
                start = i;//体现贪心
                charNum[i-1]--;
            }else{
                continue;
            }
        }

最后我们直接让start后面的所有数字统统变成9

        if(start != 0){
            for(int i = start;i < charNum.length;i++){
                charNum[i] = '9';
            }
        }

然后我们再使用 Intetger.parseInt这个函数，能帮助我们让字符串转换成整数 

最终代码如下

    public int monotoneIncreasingDigits(int n) {
        String num = String.valueOf(n);
        char[] charNum = num.toCharArray();

        int start = 0;

        for(int i = charNum.length - 1;i >= 1;i--){
            if(i > 0 && charNum[i] < charNum[i-1]){
                start = i;//体现贪心
                charNum[i-1]--;
            }else{
                continue;
            }
        }

        if(start != 0){
            for(int i = start;i < charNum.length;i++){
                charNum[i] = '9';
            }
        }
        //确保转换成的是十进制的数字
        return Integer.parseInt(String.valueOf(charNum),10);
    }

53. 最大子数组和

 根据题意：找出一个具有最大和的连续子数组

那么我们只要保证和是最大的就行了

使用贪心算法 局部最优：遍历数组的同时记录和的大小，当和小于0时果断让和变成0

全局最优：找出一个具有最大和的连续子数组

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < nums.length;i++){
            //统计和的大小
            sum += nums[i];
            //不断地比较从而得出最大和
            max = Math.max(sum,max);
            if(sum <= 0){
                sum = 0;
            }
        }
        return max;
    }
}

贪心算法解决股票问题

122. 买卖股票的最佳时机 II

 根据题意，这题使用贪心算法

局部最优：利润大于0才买入，当利润小于等于0立马卖掉，全局最优是得到最大利润

那么根据这个思想来编写代码

for(int i = 1;i < price.length;i++){
    int sum = price[i] - price[i-1];
    if(sum > 0){
        ans += sum;
    }else{
        continue;
    }
}

 最后贴出全部的代码

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        if(prices.length == 1){
            return ans;
        }
        for(int i = 1;i < prices.length;i++){
            int sum = prices[i] - prices[i-1];
            if(sum > 0){
                ans += sum;
            }else{
                continue;
            }
        }
        return ans;
    }
}

思考如何从两个维度使用贪心算法解决问题

当我们遇到需要从两个维度来解决问题的题目时，如果我们同时思考两个维度，那么很有可能就会顾此失彼，所以我们的策略就是单独来思考两个维度的其中之一，最后结合两个解决方案

406. 根据身高重建队列

根据题意 “每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人”，我们很容易的能推导出本题需要从两个维度来解决问题，一个是身高，一个是位置

那么我们就根据策略单独来思考两个维度的其中之一，最后结合两个解决方案来解决问题

首先我们根据身高来进行排序

那么我们就写出一个排序算法，根据身高从大到小来进行排序

        Arrays.sort(people,(a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });

这个时候身高这个维度以及解决了，那么就来解决位置这个维度

根据题意：“前面正好有 ki 个身高大于或等于 hi 的人”，可以推导出我们需要根据数组中下标为1的元素再次进行排序（因为数组中下标为1代表着前面还有多少人）

我们可以使用链表来进行再次排序，根据数组中下标为1的元素插入到链表中对应下标的位置，从而实现了两个维度 “每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人”，既保证了数组是从高到低来进行排序的，又满足了前面正好有 ki 个身高大于或等于 hi 的人

最后贴出完整代码

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });

        LinkedList<int[]> list = new LinkedList();

        for(int[] i : people){
            list.add(i[1],i);
        }

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

135. 分发糖果

这道题目也是经典的从两个维度来思考问题：

• 相邻两个孩子评分更高的孩子会获得更多的糖果

相邻也就代表着有左边相邻也有右边相邻，如果我们在遍历数组的过程中同时思考左右两边很容易顾此失彼，那么我们还是使用我们的解题策略：独来思考两个维度的其中之一，最后结合两个解决方案

我这里给出一个例子

我们首先思考比左边孩子评分更高的情况，再来思考比右边孩子评分更高的情况

最后得出下面这个分析过程

我们根据分析过程来编写代码，最终得到如下结果

class Solution {
    public int candy(int[] ratings) {
        int[] ratingsVec = new int[ratings.length];
        Arrays.fill(ratingsVec,1);
        for(int i = 1;i < ratings.length;i++){
            if(ratings[i] > ratings[i-1]){
                ratingsVec[i] = ratingsVec[i-1] + 1;
            }
        }
        for(int i = ratings.length - 2;i >= 0;i--){
            if(ratings[i] > ratings[i+1]){
                ratingsVec[i] = Math.max(ratingsVec[i],ratingsVec[i+1] + 1);
            }
        }
        int sum = 0;
        for(int i : ratingsVec){
            sum += i;
        }
        return sum;
    }
}

使用贪心算法解决区间问题

1.跳跃游戏问题

跳跃问题的解题关键就在于寻找到可以跳跃到达的最远下标位置

55. 跳跃游戏

根据题意：数组中的每个元素代表你在该位置可以跳跃的最大长度

换言之：数组中的每个元素 都代表着 该下标开始能到达最远区间是多少

那么只要区间包含到最后一个下标，那么就一定可以到达最后一个下标

我们使用for循环来模拟跳跃的过程，在模拟的过程中不断的更新区间，在更新区间的时候我们使用贪心算法，局部最优：每次更新都更新最大的区间 全局最优：到达最后一个下标

    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int cover = 0;
        for(int i = 0;i <= cover;i++){
            if(i >= nums.length - 1){
                return true;
            }
            cover = Math.max(cover,i + nums[i]);
        }
        return false;
    }

45. 跳跃游戏 II

这题同样也是跳跃问题

这道题目求的是到达最后一个下标所需要的最小次数

大体思路还是一样的，都是找到最远下标来解决问题

我们还是不断的寻找最远区间，但是区别在于每次到达最远下标的时候都更新次数，同时再次走寻找到的最远区间

当我们走到终点前的一步，发现此时还是不能走到终点，那么此时就应该再将步数加一次同时推出循环避免操作空指针

    if(i == cur){            
        cur = next;
        ans++;
        if(next >= nums.length - 1){
            break;
        }              
    }

最后贴出最终代码

class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int cur = 0;
        int next = 0;
        if(nums.length == 1){
            return 0;
        }
        for(int i = 0;i < nums.length;i++){
            next = Math.max(next,i + nums[i]);
            if(i == cur){            
                cur = next;
                ans++;
                if(next >= nums.length - 1){
                    break;
                }              
            }

        }
        return ans;
    }
}

2.重叠区间问题

重叠区间问题的解题关键就在于找到重叠的区间后 修改区间 然后再次进行寻找

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

我们想要用最少数量的弓箭引爆应可能多的气球，那么我们就要尽量让气球重叠在一起

我们可以先让数组从小到大进行排序，然后寻找重叠的区间，当我们找到了重叠的区间就更新终止下标的位置，如果没有找到，那么就说明又需要一支弓箭来射爆下一组重叠的气球了

根据我画出来的这副分析图可以发现，当我们找到了重叠的区间以后，就应该更新原本终止下标的位置（改成重叠区间内的终止下标）。这样就能保证寻找到的下一个区间也是在重叠区间内，否则就要让弓箭数加一

分析完成后代码就好写了

    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,((a, b) -> Integer.compare(a[0], b[0])));

        int ans = 1;

        for(int i = 1;i < points.length;i++){
            //没有找到重叠的区间
            if(points[i][0] > points[i-1][1]){
                ans++;
            }else{
                //找到了重叠的区间然后修改下标
                points[i][1] = Math.min(points[i][1],points[i-1][1]);
            }
        }

        return ans;
    }

435. 无重叠区间

根据题意：需要移除区间的最小数量，使剩余区间互不重叠

翻译过来就是寻找到重叠的区间，那么本题代码就和上题差不多了，只不过我们要把ans放进寻找重叠区间的逻辑里面

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int ans = 0;

        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0] >= intervals[i-1][1]){
                continue;
            }else{
                ans++;
                //不能是intervals[i][1] = intervals[i-1][1];如果前一个长 现在的短那么也会导致重复
                intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }

        return ans;
    }
}

56. 合并区间

合并区间说白了也是寻找到重叠的区间然后再进行合并操作

那么大体的逻辑还是和上面的两题一样，只不过具体操作有所不同：

我们以起始下标为起点，不断地寻找最远的终止下标

所以我们就需要两个变量一个起始下标 一个终止下标

 当我们找不到重叠区间了，说明此时我们就要更新起始下标了，寻找下一个重叠区间

当我们找到重叠去建立，说明此时就要更新终止下标，获取最远的终止下标（贪心）

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b) -> {
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        LinkedList<int[]> list = new LinkedList();
        
        //初始化
        int left = intervals[0][0];
        int right = intervals[0][1];

        for(int i = 1;i < intervals.length;i++){
            //没有找到重叠区间
            if(intervals[i][0] > right){
                int[] res = new int[2];
                res[0] = left;
                res[1] = right;
                list.add(res);
                left = intervals[i][0];
                right = intervals[i][1];
            //找到了重叠的区间
            }else{
                right = Math.max(intervals[i][1],right);
            }
        }
        //最后一个合并区间添加到链表里面
        int[] res = new int[2];
        res[0] = left;
        res[1] = right;
        list.add(res);

        return list.toArray(new int[list.size()][]);
    }

3.结合跳跃问题和重叠区间问题 

763. 划分字母区间

根据题意 我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中

首先我们可以遍历字符串，寻找到每个字母最远能够到达的下标的位置，并且记录下来

然后我们再次选择遍历字符串，同时使用一个变量来记录当前能够到达的最远的位置，同时通过比较不断的修改当前能够到达的最远下标的位置

当我们到达了最远下标时，说明此时我们找到了区间即同一字母最多出现在一个片段中的区间内

    public List<Integer> partitionLabels(String s) {
        int[] edge = new int[26];
        ArrayList<Integer> list = new ArrayList();

        for(int i = 0;i < s.length();i++){
            edge[s.charAt(i) - 'a'] = i;
        }

        int left = -1;
        int right = 0;
        int index = 0;

        for(int i = 0;i < s.length();i++){
            index = Math.max(index,edge[s.charAt(i) - 'a']);
            if(i == index){
                right = i;
                list.add(right - left);
                left = i;
            }
        }

        return list;
    }

两道难题

134. 加油站

这道题目如果我们使用模拟的方式来进行解题也是可以的，但是很显然太过于麻烦了

那么我们换一种思路，由于每个加油站都有耗油量和加油量，那么如果我们将他们进行整合一下

路过每个加油站都会得出一个剩油量（加油量 - 耗油量）

同时让车辆从起点开始路过每个加油站的时候都统计一下剩下的油量

如果剩下的油量小于0说明不能再往前开了，此时就得选择下一个站点作为起始位置重新计算了

由于我们是需要将车辆跑一圈（从起始位置出发最终回到起始位置），有没有一种可能就是如果我们选择了下一个站点作为起始位置，那么由于只能知道以下一个站点为起始位置后面的剩油量，不知道前面的剩油量从而导致不能跑完全程？

答案是有可能的，所以我们要先确定好车辆能不能够跑完全程

方法也很简单，只要确定gas之和大于等于cost之和，那么就一定是可以跑完全程的

        for(int i = 0;i < rest.length;i++){
            rest[i] = gas[i] - cost[i];
            sum += rest[i];
        }

        if(sum < 0){
            return -1;
        }

还有一种常见的疑惑，由于我们从起始加油站跑到 i 这个站点的时候剩油量小于0了，我们直接让 i + 1作为起始位置重新开始跑，那么有没有一种可能就是 起始位置到 i 之间再选择一个位置作为起始位置，从而使到达 i 这个位置的时候剩油量大于0？换言之会不会遗漏掉某一个起始位置？

那么我画一幅图来进行解释

那么根据我这副图的分析就能够很好的解释这种现象了，所以根本就不会出现这样的问题，因为我们的策略就是 剩下的油量小于0说明不能再往前开了，此时就得选择下一个站点作为起始位置重新计算了，不存在说会遗漏掉某一个起始位置

最后贴上我们的最终代码

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] rest = new int[gas.length];

        int sum = 0;

        for(int i = 0;i < rest.length;i++){
            rest[i] = gas[i] - cost[i];
            sum += rest[i];
        }

        if(sum < 0){
            return -1;
        }

        sum = 0;
        int ans = 0;

        for(int i = 0;i < rest.length;i++){
            sum += rest[i];
            if(sum < 0){
                sum = 0;
                ans = i + 1;//下一个加油站开始
            }
        }

        return ans;
    }
}

968. 监控二叉树

这道题可以说是一道难题了

根据示例

同时结合题目意思：每个摄影头都可以监视其父对象、自身及其直接子对象，也就是说每个摄像头只能监控他的相连接的节点

这个时候分情况讨论出局部最优

从而达到全局最优：计算监控树的所有节点所需的最小摄像头数量

首先我们约定好：

为了充分利用上中下三个位置的节点状态，我们应该使用后序遍历，从下往上的遍历二叉树

同时函数返回值是返回状态，我们使用 int 来接收

当返回值为0时为没有被监控的状态

当返回值为1时为放置了摄像头的状态

当返回值为2时为被摄像头监控的状态

情况1：当节点是叶子节点的时候

当节点是叶子节点，那么此时我们就让他的父节点装一个监控，从而达到用最少的摄像头数量监控最多的节点

        if(root == null){
            return 2;
        }

情况2：当两个节点都有子节点有监控时，此时父节点就不需要安装摄像头了 

        if(left == 1 && right == 1){
            return 2;
        }

情况3：当左右孩子有一个有摄像头时

并且另一个节点被监控到了，此时父节点就不需要安装摄像头了

        if(left == 1 || right == 1){
            result++;
            return 2;
        }

情况4：当左右孩子有一个没有被监控到，那么此时父节点不过另一个节点是否安装了摄像头它一定要安装摄像头

        if(left == 0 || right == 0){
            result++;
            return 1;
        }

情况5：当头节点没有被监控，那么就给头节点添加一个监控

if(root == 0){
    root.val = 1;
    result++;
}

 

 

分析完毕，现在开始编写代码

class Solution {
    int result = 0;
    public int minCameraCover(TreeNode root) {
        if(minCameraCoverHelper(root) == 0){
            result++;
        }
        return result;
    }

    public int minCameraCoverHelper(TreeNode root){
        if(root == null){
            return 2;
        }

        int left = minCameraCoverHelper(root.left);
        int right = minCameraCoverHelper(root.right);

        if(left == 0 || right == 0){
            result++;
            return 1;
        }

        if(left == 2 && right == 2){
            return 0;
        }

        if(right == 1 || left == 1){
            return 2;
        }

        return -1;
    }
}

代码编写完毕