贪心算法总结

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

455. 分发饼干

局部最优就是大饼干喂给大胃口的，充分利用饼干尺寸喂饱一个。全局最优就是喂饱尽可能多的小孩。

1. 先将饼干数组和小孩数组排序。
2. 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

3. 先用for循环遍历的小孩胃口；再用一个 index 控制饼干数组的遍历，只有符合条件，才采用自减的方式移动。

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index = s.length-1;int res = 0;for(int i=g.length-1; i>=0; i--){if(index>=0 && s[index] >= g[i]){index--;res++;}}return res;}
}

 376. 摆动序列

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以，不用做删除的操作

1. 遍历下标 i ，计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 就需要统计。
2.  考虑三种情况：

• 情况一：上下坡中有平坡
  •  (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
• 情况二：数组首尾两端
  • result 初始为 1（默认最右面有一个峰值）, 

    int preDiff = 0; // 前一对差值

• 情况三：单调坡中有平坡

  • 不能实时更新 prediff。只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。

class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;if(n <=1 ) return n;int preDiff = 0;int curDiff = 0;int res = 1;for(int i=1; i<n; i++){curDiff = nums[i]-nums[i-1];if((curDiff <0 && preDiff>=0) || (curDiff>0 && preDiff<=0)){res++;preDiff = curDiff;}}return res;}
}

53. 最大子数组和

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;if(n==1) return nums[0];int res = Integer.MIN_VALUE;int count = 0;for(int i=0; i<n; i++){count += nums[i];res = Math.max(res,count);// 这里一定不要忽略，遇到负数，置零，重开if(count<0){count=0;}}return res;}
}

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

多次买卖一支股票

利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

局部最优：收集每天的正利润，全局最优：求得最大利润。

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int res = 0;// 注意第1天没有利润for(int i=1; i<n; i++){res += Math.max(prices[i]-prices[i-1],0);}return res;}
}

55. 跳跃游戏

局部最优解：每次取最大跳跃步数（取最大覆盖范围），

整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。

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

45. 跳跃游戏 II

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。

整体最优：一步尽可能多走，从而达到最少步数。

精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了。

class Solution {public int jump(int[] nums) {int res=0;// 当前覆盖的最远距离下标int cover =0;// 下一步覆盖的最远距离下标int tmp =0;for(int i=0; i<=cover && cover<nums.length-1;i++){tmp = Math.max(tmp, nums[i]+i);if(i==cover){cover = tmp;res++;}}return res;}
}

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

 局部最优：让绝对值大的负数变为正数，当前数值达到最大

整体最优：整个数组和达到最大。

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int n = nums.length;nums = IntStream.of(nums).boxed().sorted((a,b)->Math.abs(b)-Math.abs(a)).mapToInt(Integer :: intValue).toArray();for(int i=0; i<n; i++){if(nums[i]<0 && k>0){nums[i] = -nums[i];k--;}}if(k % 2 == 1) nums[n-1] = -nums[n-1];return Arrays.stream(nums).sum();}
}

134. 加油站

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

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

406. 根据身高重建队列

在按照身高从大到小排序（身高相同的话则k小的站前面）后：

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a,b)-> a[0] == b[0] ? a[1]-b[1] : b[0]-a[0]);LinkedList<int[]> res = new LinkedList<>();for(int[] p : people){res.add(p[1], p); // Linkedlist.add(index, value)，將value插入到指定的index。}return res.toArray(new int[people.length][]);}
}

621. 任务调度器

class Solution {public int leastInterval(char[] tasks, int n) {// 统计每种任务的次数int[] count = new int[26];for(int i=0; i<tasks.length; i++){count[tasks[i]-'A'] += 1;}// 排序，找到次数最多的任务Arrays.sort(count);// 初始的最短时间minLen：（冷却时间+1） * （次数-1） +1int minLen = (n+1) * (count[25]-1) +1;// 剩余任务安排// 1.次数与最多的一样，初始时间minLen就得+1// 2.次数比最多少，直接插在冷却的位置，直到冷却的位置已满for(int i=24; i>=0; i--){if(count[i]==count[25]) minLen++;}// 若冷却的位置能被插满，最短的时间就是task.length// 否则，最短时间就是minLenreturn Math.max(tasks.length, minLen);}
}