力扣爆刷第176天之贪心全家桶（共15道题）

力扣爆刷第176天之贪心全家桶（共15道题）

零、贪心算法的解题思路：

贪心类别的题目没有啥明确的特征，只要可以从局部最优推出全局最优即可。

一、455. 分发饼干

题目链接：https://leetcode.cn/problems/assign-cookies/description/
思路：本题是有一个需求数组和一个饼干数组，饼干里的值必须大于等于需求里的值，然后让求最多可以满足多少需求。其实从解题的角度来想，本质上就想让你尽可能的在满足需求时，减少饼干的浪费，最好饼干可以刚好满足需求，这样可以流出更大的饼干来满足更大的需求，这样做就可以达到局部最优，推导到全局也可以满足全局最优。
具体做法：把需求和饼干数组都排序，然后小往大逐个匹配计数即可。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int i = 0, j = 0;
        while(i < g.length && j < s.length) {
            if(g[i] <= s[j]) {
                i++;
                count++;
            }
            j++;
        }
        return count;
    }
}

二、376. 摆动序列

题目链接：https://leetcode.cn/problems/wiggle-subsequence/description/
思路：给一个数组，求最长的摆动序列，所谓摆动序列，指的就是每一个值与前一个值的差值所组成的序列是一正一负交替出现的。求的话很好求，只需要构造一个开始状态，然后记录交替状态，关键点在于构造初始状态，需要记录前一个差值状态和当前差值状态。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length == 1) return 1;
        int count = 1;
        boolean flag = true, pro = false;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[i-1]) continue;
            boolean cur = nums[i] - nums[i-1] > 0;
            if(flag) {
                pro = !cur;
                flag = false;
            }
            if(pro != cur) {
                pro = cur;
                count++;
            }
        }
        return count;
    }
}

三、53. 最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
思路：求最大子数组和，数组中有正有负，从局部来讲，只要元素累加和为负，直接重新开始累加，期间一直统计最大值，这样局部可以达到最优，整体也可以达到最优。

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            if(sum < 0) sum = 0; 
        }
        return max;
    }
}

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
思路：买卖股票，要求可以在每一天之内都能买入或者卖出，求最大利润，那么既然可以每一天都能进行买卖操作，那么要今天的价格低于明天的价格，那么我就可以进行买卖，这就是局部最优，由此也可以达到全局最优。

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

五、55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/description/
思路：所谓跳跃游戏，即只有有一个数组，数组中的元素值代表可以向前跳跃的距离，问能否从索引为0的位置跳跃到数组尾部，其实很简单，只需要维护一个记录，记录当前可以跳跃到的最远距离，只要当前所处的位置没有超出最远跳跃距离，那么就可以继续向下跳跃，并且在跳跃的过程中不断的去更新最远距离。

class Solution {
    public boolean canJump(int[] nums) {
        int max = nums[0];
        for(int i = 0; i < nums.length; i++) {
            if(i > max) return false;
            if(i + nums[i] > max) max = i + nums[i];
        }
        return true;
    }
}

六、45. 跳跃游戏 II

题目链接：https://leetcode.cn/problems/jump-game-ii/description/
思路：和上一题类似，但是求的是最小跳跃次数，其中只要能够维护一个当前的跳跃区间，并且在区间内部记录下，下一条最远可以抵达的位置，那么只要当前区间抵达尾部，就可以把区间尾部更新为下一跳，跳跃次数也就+1，这样每次跳跃都选择当前区间内最远可以抵达的位置，就一定是最小跳跃次数。
从初始化的角度来看，nums = [0]，跳跃次数是0次，说明次数 i = 0, end = 0, max = 0。那么当索引 max >= len - 1说明可以直接返回，当 i = end时要更新end=max。

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

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

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
思路：给一个数组，求k次取反后的最大化的数组和，本质上来说求最大值非常符合贪心的策略，我们只需要有限把所有的负数在k没消耗完之前，优先替换成负数，这样可以尽可能的贴近最大值，当把所有的负数都转变成正数以后，如果k没有耗尽，此时需要分情况来看：
1、看看 i == len， 此时说明，原本的数组，全部都是负数，那么只需要对数组最后一个元素按照 nums[i] = k % 2 == 0 ? nums[i] : -nums[i]; 进行运算。
2、如果 i == 0 || nums[i] == 0，此时说明，要不是原数组全为正数，或者存在一个0，也只需要对当前索引所在位置，按照 nums[i] = k % 2 == 0 ? nums[i] : -nums[i]; 进行运算。
3、如果不是以上情况，说明当前索引停留的位置是原数组中，正负数的交界，那么只需要比较nums[i-1] 和 nums[i]的大小，选择最小的一个进行按照 nums[i] = k % 2 == 0 ? nums[i] : -nums[i]; 进行运算。
通过上面的贪心策略，即先排序，然后消耗k把所有的负数变成正数，最后围绕原数组的正负数边界挑选最小值进行处理。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0, len = nums.length;
        for(; i < len; i++) {
            if(k == 0 || nums[i] >= 0) break;
            nums[i] = -nums[i];
            k--;
        }
        if(k > 0) {
            if(i < len) {
                if(i - 1 > 0 && nums[i-1] < nums[i]) i = i-1;
                nums[i] = k % 2 == 0 ? nums[i] : -nums[i];
            }else{
                nums[len-1] = k % 2 == 0 ? nums[len-1] : -nums[len-1];
            }
        }
        int sum = 0;
        for(int t : nums) {
            sum += t;
        }
        return sum;
    }
}

八、134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/description/
思路：加油站这个题也是个经典题目了，给两个数组，一个数组表示油量，一个数组表示消耗量，让找到可以跑完一圈的起点。
其实思路非常简单，先说第一个概论，一定是在总油量大于等于消耗量时才能跑完完整的一圈。
满足了上面说的这个，然后我们再往下谈。
接下来只需要做遍历即可，只要油量与消耗量的差值的累加和小于0，就说明当前位置不是开始位置，我们就可以把开始位置更新为下一个位置，并且把累加和置零，这个做法可以方便的更新开始位置，而且一定只有油量大于消耗量的位置才可能算是起始位置。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int cur = 0, total = 0, start = 0;
        for(int i = 0; i < gas.length; i++) {
            cur += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        if(total < 0) return -1;
        return start;
    }
}

九、135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/description/
思路：分发糖果，这也是一个典型的题目了，要求如果一个值大于它左右相邻的值，那么它获得的糖果数量应该大于它左右相邻值获得的糖果数量，听起来很简单，但是需要分开来看，一次性，同时考虑左边的条件，并且也考虑右边的条件，实现起来很复杂，但我们解决复杂问题，可以把他们拆分开再来处理，可以先处理左边，然后再处理右边。
先处理左边：直接遍历，如果当前元素大于左边元素，那么当前元素获得的糖果值应该为 nums[i] = nums[i-1] + 1.需要比左边多1个。
然后再处理右边的值：直接从右边进行遍历，如果当前元素值大于右边边的元素，并且，当前已经获得的糖果数是小于等于右边的，也就是当 ratings[i] > ratirng[i+1] && nums[i] <= nums[i+1] 时才需要更新当前的糖果值为 nums[i] = nums[i+1] + 1.

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] nums = new int[len];
        for(int i = 1; i < len; i++) {
            if(ratings[i] > ratings[i-1]) nums[i] = nums[i-1] + 1;
        }
        for(int i = len-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1] && nums[i] <= nums[i+1]) nums[i] = nums[i+1] + 1;
        }
        int sum = 0;
        for(int i : nums) sum += i;
        sum += len;
        return sum;
    }
}

十、860. 柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/
思路：本题是个简单题，在遍历的过程中，对5元、10元的数量进行统计和维护，进行正常的增加和扣减，如果出现扣减失败的情况，就无法找零。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int a = 0, b = 0;
        for(int i : bills) {
            if(i == 5) {
                a++;
            }else if(i == 10) {
                if(a > 0) {
                    a--;
                    b++;
                }else return false;
            }else {
                if(b > 0 && a > 0) {
                    b--;
                    a--;
                }else if(b <= 0 && a > 2) {
                    a -= 3;
                }else return false;
            }
        }
        return true;
    }
}

十一、406.根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/description/
思路：根据身高重建队列，这也是一个经典题目了，其实和上面的分糖果的题非常的类似，分糖果的题是需要分别考虑左边和右边，本题也一样，也需要分别考虑，身高的排列，和排队人数的排列，都是各有两个维度，两个维度一块考虑比较难处理，可以一个一个维度的处理。
本题就两个维度：身高和数量，那考虑维度有没有先后呢？在不清楚的时候可以自己试一试看看合不合理，假设先按照数量排序，排完以后很乱也看不出来什么规律，那如果先按照身高排序呢？会发现，按照身高降序排列，身高相同的数量俺升序排序，是基本符合要求的，且对于每一个元素来说，他前面排队的人的数量，对应的索引位置，插入进去后，前面比他高的人的数量正好是索引前面元素的数量。
初始队列： [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
按照身高降序，相同按照排队人数升序排列：[[7, 0], [7, 1], [6, 1], [5 0], [5, 2], [4, 4]]
后面就该按照排队人数进行插入然后移动元素了，但是为了避免移动元素带来的性能损耗，可以使用LinkedList进行插入，链表非常适合这种写多读少的场景。

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[] t : people) {
            list.add(t[1], t);
        }
        return list.toArray(new int[list.size()][]);
    }
}

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

题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
思路：区间类型的题目也是贪心的常客了，本题是有很多气球，气球是有宽度的，位于不同的区间，问想要引爆这些气球，最少需要多少根箭，其实求最值问题一般都是贪心，我们要想用尽可能少的箭引爆尽可能多的气球，那么就应该按照气球的坐标排序，所有重叠的气球用1根箭，这样数量才最少，所以具体做法就是，按照左边界进行升序排列，然后遍历区间，如果当前气球的左边界，大于维护的重叠区间的右边界，相当于没有重叠，那么箭的数量就得加1根，如果当前气球的左边界小于维护的重叠区间的右边界，那么更新重叠区间的右边界为两个右边界的最小值，维护重叠区间。

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 1, right = points[0][1];
        for(int i = 0; i < points.length; i++) {
            if(points[i][0] > right) {
                count++;
                right = points[i][1];
            }else{
                right = Math.min(right, points[i][1]);
            }
        }
        return count;
    }
}

十二、435. 无重叠区间

题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/
思路：无重叠区间，本题和上一题类似，正好是反过来了，上一题其实求的是重叠区间的数量，本题求的是无重叠区间的数量，那么怎么能够通过减少最少的区间，来达到无重叠区间的目的呢？首先要做的呢还是按照所有区间的左边界进行排序，之后我们统一维护一个右边界，然后遍历剩余区间，只要当前区间的左边界大于等于维护区间的右边界，那么就是无重叠，直接把维护的右边界替换成当前区间的右边界，但是如果当前区间的左边界小于维护区间的右边界，那么就是重叠了，但是重叠了，是改把维护的区间给区间，还是把当前的区间给去掉，其实很简单，一定要去掉占地面积大的区间，这样才能达到去掉的区间数量最少，所以只需要把维护区间的右边界替换成，这两个右边界的最小值，也就是保留占地范围更小的区间。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int count = 0, right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= right) {
                right = intervals[i][1];
            }else{
                count++;
                right = Math.min(right, intervals[i][1]);
            }
        }
        return count;
    }
}

十三、763. 划分字母区间

题目链接：https://leetcode.cn/problems/partition-labels/description/
思路：所谓划分字母区间，要求的是尽可能多的把字符串分割成多个片段，但让字母只出现一个片段里，而不要跨片段出现。这么一看其实也不难，我们只需要先遍历一遍字符串，记录下每种字符出现的最远距离。
然后在遍历字符串，一边遍历，一边更新当前出现过的字符的最远距离，如果当前遍历的位置已经抵达了出现过的字符串的最远处了，说明，当前出现过的所有类别的字符，都不会在后序出现了，这个位置就是一个划分的边界，然后记录划分的边界，更新左边界。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] nums = new int[26];
        for(int i = 0; i < s.length(); i++) {
            nums[s.charAt(i) - 'a'] = i;
        }
        int max = 0, pro = -1;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < s.length(); i++) {
            max = Math.max(max, nums[s.charAt(i) - 'a']);
            if(i == max) {
                list.add(i - pro);
                pro = i;
            }
        }
        return list;
    }
}

十四、56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/description/
思路：这是区间相关的第3道题目了，前面有引爆气球、无重复区间，这题是合并区间，相比于前面的两题来说简单多了，维护好一个最大区间，用当前区间的左边界与最大区间的右边界进行比较，如果大于右边界，说明无法合并，就把最大区间保存，然后更新最大区间为当前区间。如果当前区间的左边界小于等于最大区间的右边界，那么说明是可以合并的，只需要把最大区间的右边界，更新为两个右边界的最大值即可。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int left = intervals[0][0], right = intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] > right) {
                list.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }else{
                right = Math.max(right, intervals[i][1]);
            }
        }
        list.add(new int[]{left, right});
        return list.toArray(new int[list.size()][]);
    }
}

十五、738. 单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/
思路：给了一个数字，想求一个最接近这个数的，一个从高位到低位递增的一个数，其实很好求，只需要先把这个数转成字符串再转成字符数组，然后从数组尾部开始往首部遍历，只要发现逆序对，如nums[i] > nums[i+1]，那么把nums[i]–，然后记录下i+1的位置，因为只要发生了逆序对，那么就得把前一个数减一，然后后面的数为了更加接近原数，就需要全部取9.
至于遍历的顺序为什么是从后往前，因为如果从前往后就会出现，3,2,1，的情况，3>2,3–为2,2,1，然后2 > 1,2–，为2,1,1。因为要求的是递增，但往后遍历自减的过程中，可能影响前面已经维护好的递增顺序。

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] nums = s.toCharArray();
        int k = nums.length;
        for(int i = nums.length - 2; i >= 0; i--) {
            if(nums[i] > nums[i+1]) {
                nums[i]--;
                k = i + 1;
            }
        }
        for(int i = k; i < nums.length; i++) {
            nums[i] = '9';
        }
        return Integer.parseInt(String.valueOf(nums));
    }
}