目录
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法；贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。
玄学贪心，但是掌握的几道题目！
贪心常见的经典应用场景有如下这些，这些算法很多与图有关，本身比较复杂，也难以实现 ，我们一般掌握其思想即可：
排序问题：选择排序、拓扑排序
优先队列：堆排序
赫夫曼压缩编码
图里的Prim、Fruskal和Dijkstra算法
硬币找零问题
分数背包问题
并查集的按大小或者高度合并问题或者排名
任务调度部分场景
一些复杂问题的近似算法
分发饼干
假设你要给孩子们一些小饼干。
要求与说明:
1.每个孩子最多只能给一块饼干。
2.每个孩子的饭量不同，对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；
3.每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
4你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例，其中g是胃口，s是拥有的饼干：
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。
解题思路：
这里既要满足小孩的胃口，也不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。所以，这里可以使用贪心策略，先将饼干数组和小孩数组排序。 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量就可以了。
// 大饼干先喂饱大胃口，最后看能满足几个孩子的需要就行。
//g是孩子的胃口数组，s是拥有的饼干数组
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
// 遍历孩子的胃口
for (int index = g.length - 1; index >= 0; index--) {
if(start >= 0 && g[index] <= s[start]) {
start--;
count++;
}
}
return count;
}柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例2：
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
解题思路：
如果给的是5，那么直接收下。
如果给的是10元，那么收下一个10，给出一个5，此时必须要有一个5才行。
如果给的是20，那么优先消耗一个10元，再给一个5元。假如没有10元，则给出3个5元。【先给10】
public boolean lemonadeChange(int[] bills) {
//这里只表示5元和10元纸币的数量，而不是总金额
int cash_5 = 0;
int cash_10 = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
cash_5++;
} else if (bills[i] == 10) {
cash_5--;
cash_10++;
} else if (bills[i] == 20) {
if (cash_10 > 0) {
cash_10--;
cash_5--;
} else {
cash_5 -= 3;
}
}
if (cash_5 < 0 || cash_10 < 0) return false;
}
return true;
}分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果，并返回需要准备的 最少糖果数目：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
示例1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
public int candy(int[] ratings) {
int[] candyVec = new int[ratings.length];
candyVec[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candyVec[i] = candyVec[i - 1] + 1;
} else {
candyVec[i] = 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int s : candyVec) {
ans += s;
}
return ans;
}区间问题
判断区间是否重叠
给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。
示例 1:：
输入: intervals = [[0,30],[15,20],[5,10]]
解释: 存在重叠区间，一个人在同一时刻只能参加一个会议。
解题思路：将区间按照会议开始时间进行排序，然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束即可。
public boolean canAttendMeetings(int[][] intervals) {
// 将区间按照会议开始实现升序排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历会议，如果下一个会议在前一个会议结束之前就开始了，返回 false。
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
return true;
}合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
解题思路：对区间按照起始端点进行升序排序，然后逐个判断当前区间是否与前一个区间重叠，如果不重叠的话将当前区间直接加入结果集，反之如果重叠的话，就将当前区间与前一个区间进行合并。
public int[][] merge(int[][] intervals) {
// 先按照区间起始位置排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历区间
int[][] res = new int[intervals.length][2];
int idx = -1;
for (int[] interval: intervals) {
// 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，说明不重叠。
// 则不合并，直接将当前区间加入结果数组。
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
// 反之说明重叠，则将当前区间合并至结果数组的最后区间
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return Arrays.copyOf(res, idx + 1);
}插入区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
示例 1:：
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
解释: 新区间[2,5] 与 [1,3]重叠，因此合并成为 [1,5]。
示例 2:：
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠，因此合并成为 [3,10]。
首先将新区间左边且相离的区间加入结果集（遍历时，如果当前区间的结束位置小于新区间的开始位置，说明当前区间在新区间的左边且相离）；
接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，将最终合并后的新区间加入结果集；
最后将新区间右边且相离的区间加入结果集。
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] res = new int[intervals.length + 1][2];
int idx = 0;
// 遍历区间列表：
// 首先将新区间左边且相离的区间加入结果集
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
res[idx++] = intervals[i++];
}
// 判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
// 将最终合并后的新区间加入结果集
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
res[idx++] = newInterval;
// 最后将新区间右边且相离的区间加入结果集
while (i < intervals.length) {
res[idx++] = intervals[i++];
}
return Arrays.copyOf(res, idx);
}字符串分割
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
解题思路：
首先，统计每一个字符最后出现的位置
然后，从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。
public List<Integer> partitionLabels(String S) {
List<Integer> list = new LinkedList<>();
int[] edge = new int[26];
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
edge[chars[i] - 'a'] = i;
}
int idx = 0;
int last = -1;
for (int i = 0; i < chars.length; i++) {
idx = Math.max(idx,edge[chars[i] - 'a']);
if (i == idx) {
list.add(i - last);
last = i;
}
}
return list;
}加油站问题
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
示例1
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
解题思路：
首先，如果总油量减去总消耗大于等于零，那么应该能跑完一圈，具体到每一段就是各个加油站的剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置必须从i+1开始重新算，只有这样才能保证我们有可能完成。
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
// 当前累加rest[i]和 curSum一旦小于0
if (curSum < 0) {
// 更新起始位置为i+1
start = i + 1;
// curSum从0开始
curSum = 0;
}
}
// 说明怎么走都不可能跑一圈了
if (totalSum < 0) return -1;
return start;
}跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度，判断你是否能够到达最后一个位置。
示例1：
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例2：
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。
解题思路：
定义一个cover表示最远能够到达的方位，也就是i每次移动只能在其cover的范围内移动，每移动一次，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。而cover每次按照下面的结果判断。如果cover大于等于了终点下标，直接return true就可以了
public boolean canJump(int[] nums) {
if (nums.length == 1) {
return true;
}
//覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
int cover = 0;
//在覆盖范围内更新最大的覆盖范围
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i]);
if (cover >= nums.length - 1) {
return true;
}
}
return false;
}最短跳跃游戏
求最少到达的步数该怎么办呢？
解题思路：
贪心＋双指针
left用来一步步遍历数组
steps用来记录到达当前位置的最少步数
right表示当前步数下能够覆盖到的最大范围
我们还需要一个临时变量conver，假如left到达right时才更新right
public int jump(int[] nums) {
int right = 0;
int maxPosition = 0;
int steps = 0;
for (int left = 0; left < nums.length - 1; left++) {
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[left] + left);
if (left == right) { //遇到边界，就更新边界，并且步数加一
right = maxPosition;
steps++;
}
//right指针到达末尾了。
if (right >= nums.length - 1) {
return steps;
}
}
return steps;
}