目录

455.分发饼干

思路：

策略归纳：

55、跳跃问题

621. 任务调度器

135. 分发糖果

 435. 无重叠区间

45. 跳跃游戏 II

 总结：

---

每次根据问题的当前状态，选择一个局部最优策略，并且不断迭代，最后产生一个全局最优解。

 每次从当前问题出发，而不考虑之前或之后的状态，做出一个最有利于当前问题的决策，迭代更新问题，不断重复同样的操作直到问题得到解决。

455.分发饼干

不同大小的饼干分发给胃口不同的孩子，目标是满足尽可能多的孩子。

思路：

从孩子方面：

胃口小的应该优先满足，因为最容易满足，被成功分配的概率高

从饼干方面：

        物尽其用，当一个孩子能被多个饼干满足时，应该用最小的一个。

策略归纳：

当全局最优解涉及多个变量时，分别考虑每个变量对全局最优解的影响，最后将所有情况进行汇总考虑。

上面涉及两个变量孩子和饼干，归纳起来就是先满足胃口最小的孩子，然后饼干选可以满足的最小一块。

也就是对孩子和饼干分别排序，

55、跳跃问题

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

思路：

从贪心的思路（局部最优）走

思考，当前位置是3，那我是跳1，跳2还是跳3

（1） 如果每次都选择最远距离，而如果最远距离3可以跳跃的最大长度是0，那么就进入了死胡同。

（2）如果每次选择最近距离1，那么如果最近距离1可以跳跃的最大长度是0，那么也进入了死胡同。

（3）从上面可以看出不管选择最远距离还是最近距离还是中间的距离都会有可能陷入它的在最大长度为0的死路，那么是不是需要考虑跳的那个距离呢？

（4）考虑跳到那个位置的下标数，它那个数代表我能跳到下一个步骤的距离，如果那个距离大，那么就认为我为下一个步骤提供了最好的一步

伪代码：

1、如果数组的长度为1，返回true

2、 for遍历数组，如果当前位置加上数组的位置超过数组直接返回true

      否则判断数组的[当前位置+位置里的从0开始的数]进行循环

下面的代码以覆盖范围为主角， 刚开始覆盖范围为0，在覆盖范围内计算自己能达到的最远距离，然后更新覆盖范围，每往前走一步，如果覆盖范围超过了数组的范围，那么就成功

  public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}//覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的int coverRange = 0;//在覆盖范围内更新最大的覆盖范围for (int i = 0; i <= coverRange; i++) {coverRange = Math.max(coverRange, i + nums[i]);if (coverRange >= nums.length - 1) {return true;}}return false;}

621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

思路：

我觉得这个题的解法和贪心没有关系，如果硬套的话

局部优先，考虑次数最多的任务

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']++;}//统计词频Arrays.sort(count);//词频排序，升序排序，count[25]是频率最高的int maxCount = 0;//统计有多少个频率最高的字母for (int i = 25; i >= 0; i--) {if(count[i] != count[25]){break;}maxCount++;}//公式算出的值可能会比数组的长度小，取两者中最大的那个return Math.max((count[25] - 1) * (n + 1) + maxCount , tasks.length);}
}

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

例如

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

提示：

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
通过次数133,507提交次数273,320

class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] left_ans = new int[n];int[] right_ans = new int[n];Arrays.fill(left_ans, 1);Arrays.fill(right_ans, 1);int ans = 0;// 考虑左相邻条件for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {left_ans[i] = left_ans[i - 1] + 1;}}// 考虑右相邻条件for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {right_ans[i] = right_ans[i + 1] + 1;}}// 合并两个条件结果for (int i = 0; i < n; i++) {ans += Math.max(left_ans[i], right_ans[i]);}return ans;}
}

 435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

 局部最优推出全局最优，那就是贪心。

下面排序代码使用了泛型

java中Arrays.sort()的几种用法_barry_gfw的博客-CSDN博客_arrays.sort

class SolutionL15_5 {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> {if (a[0] == a[0]) return a[1] - b[1];return a[0] - b[0];});System.out.println(intervals);for(int i=0;i<intervals.length;i++){System.out.print(intervals[i][0]);System.out.println(intervals[i][1]);}int count = 0;int edge = Integer.MIN_VALUE;for (int i = 0; i < intervals.length; i++) {if (edge <= intervals[i][0]) {edge = intervals[i][1];} else {count++;}}return count;}
}

• 难点一：一看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排。
• 难点二：排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了。
• 难点三：直接求重复的区间是复杂的，转而求最大非重复区间个数。
• 难点四：求最大非重复区间个数时，需要一个分割点来做标记。

45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

public static  int jump(int[] nums) {if (nums == null || nums.length == 0 || nums.length == 1) {return 0;}//记录跳跃的次数int count=0;//当前的覆盖最大区域int curDistance = 0;//最大的覆盖区域int maxDistance = 0;for (int i = 0; i < nums.length; i++) {//在可覆盖区域内更新最大的覆盖区域maxDistance = Math.max(maxDistance,i+nums[i]);//说明当前一步，再跳一步就到达了末尾if (maxDistance>=nums.length-1){count++;break;}//走到当前覆盖的最大区域时，更新下一步可达的最大区域if (i==curDistance){curDistance = maxDistance;count++;}}return count;}

 总结：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。