算法训练-6高效算法部分 贪心算法
6.3 贪心算法
前言
贪心算法一般出现在笔试题中，面试出现的概率非常低。贪心算法理解并不难，他区分于我们常用DFS/BFS/DP，他并不会枚举所有情况，而是只选择其中“当前最优”的情况。因此，贪心算法的思想并不难，甚至代码也并不难实现，但是难点在于找到贪心的策略和证明贪心策略有可行性。
贪心的正确性严格意义上来说是需要数学证明的，但这超出了数据结构的范畴，特别是笔试的时候，几乎不会有充足的时间让我们去证明贪心的正确性。因此，笔试的时候更多是观察数据的范围，如果数据量比较大，我们就可以往贪心的方向去尝试，注意这里的措辞：尝试。笔试的时候贪心算法的正确性往往是试出来的。
对于贪心，如果准备时间不是非常充裕的同学，可以不用花费太多时间，知道大概思考方向即可，因为即使花费再多时间训练贪心，效果依然是不明显的。
无重叠区间
给定一个区间的集合 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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 10^5
intervals[i].length == 2
- 5 * 10^4 <= starti < endi <= 5 * 10^4题目解析
区间问题的贪心策略常见的有以下几种情况：
- 每次选择开始时间最早的
- 每次选择结束时间最早的
- 每次选择总耗时最少的
- 每次选择与最少重叠的。
此题选择策略2进行贪心。
因为结束时间越早，可选的区间就越多。这是最直观的一个解释，如果要严格地证明的话，方法如下：
- 与其他方案相比，此算法的选择方案在选取了相同数量的更早开始的区间时，其最终结束时间不会比其他方案晚。
- 因此，不存在选择更多区间的方案。
代码展示
class Solution {
// eraseOverlapIntervals 方法用于找出给定区间数组 intervals 中不重叠区间的数量
// 通过首先按照结束时间对区间进行排序，然后遍历排序后的区间数组，计算出不重叠的区间数量
public int eraseOverlapIntervals(int[][] intervals) {
// 使用 Arrays.sort 方法和 lambda 表达式按照区间的结束时间对 intervals 进行升序排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
// 初始化计数器 cnt 为 1，表示至少有一个不重叠的区间（即第一个区间）
// 初始化 pre 为第一个区间的结束时间
int cnt = 1, pre = intervals[0][1];
// 从第二个区间开始遍历排序后的 intervals 数组
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间的开始时间大于或等于 pre（即前一个区间的结束时间），
// 则说明当前区间与前一个区间不重叠，cnt 加 1
if (intervals[i][0] >= pre) {
cnt++;
// 更新 pre 为当前区间的结束时间
pre = intervals[i][1];
}
// 如果当前区间与前一个区间重叠，则跳过当前区间，pre 保持不变
}
// 返回 intervals 长度与 cnt 的差值，即为不重叠区间的数量
return intervals.length - cnt;
}
}分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1题目解析
首先将孩子数组和饼干数组排序。首先将最小的饼干尝试匹配胃口最小的孩子，如果匹配成功，那就直接考虑下一个；否则，则说明这个饼干无法做出贡献。
代码展示
class Solution {
// findContentChildren 方法用于找出能够满足所有孩子的最少饼干数量
// g 是孩子们贪婪程度的数组，数值越大表示孩子越贪婪
// s 是各种饼干的数组，数值越大表示饼干越高级
// 方法返回能够满足所有孩子的最少饼干数量
public int findContentChildren(int[] g, int[] s) {
// 使用 Arrays.sort 方法对孩子们的贪婪程度进行升序排序
Arrays.sort(g);
// 使用 Arrays.sort 方法对饼干的高级程度进行升序排序
Arrays.sort(s);
// 初始化计数器 cnt 为 0，用于记录满足的孩子数量
int cnt = 0;
// 初始化两个指针 i 和 j 分别用于遍历饼干数组 s 和孩子们的贪婪程度数组 g
int i = 0, j = 0;
// 使用 for 循环同时遍历两个数组
// 循环条件是指针 i 和 j 都在各自的数组范围内
for (; i < s.length && j < g.length; i++) {
// 如果当前饼干 s[i] 的高级程度大于等于当前孩子的贪婪程度 g[j]，则表示这个孩子可以被满足
if (s[i] >= g[j]) {
// 满足计数器 cnt 加 1
cnt++;
// 移动孩子们的贪婪程度数组的指针 j
j++;
}
}
// 返回满足的孩子数量 cnt
return cnt;
}
}买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4题目解析
由于此题不限制买卖次数，因此此题的贪心策略如下：
如果今天买明天卖可以赚钱，那么我们就执行这个操作。
代码展示
class Solution {
// maxProfit 方法用于计算在给定价格数组 prices 下，一次股票交易的最大利润
// 假设可以完成无限次交易，但每笔交易都需要在下一次购买前出售
public int maxProfit(int[] prices) {
// 初始化利润变量 profit 为 0，用于累加每次交易的利润
int profit = 0;
// 遍历 prices 数组，从第二个元素开始
for (int i = 1; i < prices.length; i++) {
// 比较当前价格与上一个价格，如果当前价格更高，说明可以卖出获得利润
if (prices[i] > prices[i - 1]) {
// 计算本次交易的利润，即当前价格与上一个价格的差额，并累加到 profit
profit += prices[i] - prices[i - 1];
}
}
// 返回计算出的总利润
return profit;
}
}