【算法笔记】汇总——贪心篇
本篇内容的主旨在于总结LeetCode中常见的贪心题涉及的基本内容，并对此做出一定的总结与归纳，算是笔者心路历程的一些许感悟。
首先，我们将贪心题按难易程度划分为如下情况：
贪心简单题
以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，分析出局部最优是什么，全局最优是什么，贪心贪的也就有理有据！
贪心算法：分发饼干
贪心算法：K次取反后最大化的数组和
贪心算法：柠檬水找零
贪心中等题
贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。
贪心算法：摆动序列
贪心算法：单调递增的数字
【笔记】：本题型涉及贪心算法的应用，题干的问题很容易理解，即求解
单调数字，且保证<=N的最大的整数。固定思维考虑模拟，但存在TTL，不能采用。并且由题意可知，需要将输入的整数转化为字符数组进行考虑，需满足下面条件时进行更新：即当且仅当str[i-1]>str[i]时，str[i-1]--,str[i]=9。
【注意】：考虑到从右向左遍历过程中，存在先单调后不单调的情况，需要记录最后满足上述条件的索引，来进行更新。
public int monotoneIncreasingDigits(int n) {
if (n == 0) {
return 0;
}
char[] arr = Integer.toString(n).toCharArray();
int start = Integer.MAX_VALUE;
for (int i = arr.length - 1; i >= 1; i--) {
if (arr[i - 1] > arr[i]) {
start = i;
arr[i - 1]--;
}
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '0' && i == 0) {
continue;
}
if (i >= start) {
res.append('9');
} else {
res.append(arr[i]);
}
}
return Integer.parseInt(res.toString());
}
贪心解决股票问题
大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说
贪心算法：买卖股票的最佳时机II
贪心算法：买卖股票的最佳时机含手续费
两个维度权衡问题
在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。
贪心算法：分发糖果
【笔记】：本题的核心在于对贪心算法的使用，需要对评分数组做从左到右何从右到左的两次贪心比较，即：第一次从左到右，得出右边评分比左边评分大的情况下，糖果的分配情况；第二次从右到左，在上述糖果分配的基础上，得出左边评分比右边评分大的情况。
综合上述贪心得到的结果，计算总量，即可得到分配的最少的糖果数目
public int candy(int[] ratings) {
int n = ratings.length;
int[] candyCnt = new int[n];
Arrays.fill(candyCnt, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candyCnt[i] = candyCnt[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyCnt[i] = Math.max(candyCnt[i], candyCnt[i + 1] + 1);
}
}
return Arrays.stream(candyCnt).sum();
}
【笔记】：本题的核心在于对贪心算法的运用，针对题干提供的两个属性，我们需要分开讨论，由于
people[i] = [hi, ki]中ki位次属性收到hi身高的影响，所以需要对输入数组进行排序，h升序，k降序，通过从头遍历，优先按身高高的people的k做为索引值来进行插入，即插入操作过后的people满足队列属性。
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[]> queue = new LinkedList<>();
for (int[] p : people) {
queue.add(p[1], p);
}
return queue.toArray(new int[people.length][]);
}
在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用list（链表）替代了vector(动态数组)，效率会高很多。
大家也要掌握自己所用的编程语言，理解其内部实现机制，这样才能写出高效的算法！
贪心难题
这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！
贪心解决区间问题
关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。
贪心算法：跳跃游戏
贪心算法：跳跃游戏II
贪心算法：用最少数量的箭引爆气球
【笔记】：本题是对贪心算法的应用，根据题干中指出的： 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为
xstart，xend， 且满足xstart ≤ x ≤ xend，则该气球会被引爆。
为达到最小化弓箭数，需要保证一弓箭尽可能多的引爆多个气球，即可以理解为：求出气球坐标的重叠数，因此我们需要对输入数组进行排序，按照气球起始位置排序或者按照气球终止位置排序皆可，本次题解采用的是前者，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
【注意】：在排序过程中，因为差值过大而产生溢出问题，即使用Integer.compare(a[0], b[0]);来进行排序比较。
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, (a, b) -> {
return Integer.compare(a[0], b[0]);
});
int res = 1;
for (int i = 1; i < points.length; i++) {
if (points[i - 1][1] < points[i][0]) {
res++;
} else {
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return res;
}
【笔记】：本题的核心在于对贪心算法的应用，由题干可知，第一印象是需要排序，求解出
重复区间，然而直接求重复区间需要考虑多种情况，即交叉，包含等，较为麻烦复杂，因此可以考虑反向求解，即得到最大非重复区间个数。
因此本题采用了按末尾点进行排序：选择末尾点相同时，起点值大的情况。从左向右遍历，优先选右边界小的区间，保证尽可能的避免交叉。
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length < 2) {
return 0;
}
Arrays.sort(intervals, (a, b) -> {
if (a[1] != b[1]) {
return Integer.compare(a[1], b[1]);
} else {
return Integer.compare(a[0], b[0]);
}
});
int res = 1, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
res++;
end = intervals[i][1];
}
}
return intervals.length - res;
}
【笔记】：本题的核心在于对贪心算法的运用，针对在区间问题中的求
合并重叠区间，需要对输入数组按左边界或右边界进行排序，本题采用按左边界排序，而后从左到右遍历数组，记录遍历过程中的最大右边界值，并和后续数组元素中的左边界进行比较，若重叠则更新旧区间的右边界，若非重叠，则更新最大右边界值，并记录该元素区间。
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> {
return a[0] - b[0];
});
ArrayList<int[]> res = new ArrayList<>();
res.add(intervals[0]);
int last = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= last) {
int[] tmp = res.get(res.size() - 1);
tmp[1] = Math.max(tmp[1], intervals[i][1]);
last = tmp[1];
} else {
res.add(intervals[i]);
last = intervals[i][1];
}
}
return res.toArray(new int[res.size()][]);
}
其他难题
贪心算法：最大子序和 其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。
贪心算法：加油站可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。
【笔记】：本题的核心在于对贪心算法的掌握，题目中车开满全程需要满足两个条件：所有站的加油量
>=车所有站的耗油量，当在区间[i,j]
的车剩余油量<0,则起始点至少为j+1。
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0, start = 0, totalSum = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
start = i + 1;
curSum = 0;
}
}
if (totalSum < 0) {
return -1;
}
return start;
}
最后贪心系列压轴题目贪心算法：我要监控二叉树，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。
【笔记】：本题的核心在于贪心算法的应用，由题意可以发现，题目示例中的摄像头都没有放在叶子节点上。
针对输入的二叉树，从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少。
我们需要输入二叉树进行后序遍历得到从下往上的迭代，并根据左右子节点的状态关系，对父节点的状态进行更新。
我们将状态关系列为如下三种，即0：无覆盖，1：摄像头存在，2：有覆盖，因此存在如下三种子节点情况：
1、左右子节点皆处于覆盖状态，则父节点无覆盖； 2、左右子节点至少一个处于无覆盖状态，则父节点需要设置摄像头；3、左右子节点至少一个处于摄像头存在状态，则父节点为覆盖状态。
【注】：需要考虑根节点覆盖状态
int cnt = 0;
public int minCameraCover(TreeNode root) {
if (trval(root) == 0) {
cnt++;
}
return cnt;
}
/**
* 0:无覆盖,1:摄像头,2:有覆盖
*
* @param root
* @return
*/
private int trval(TreeNode root) {
if (root == null) {
return 2;
}
int left = trval(root.left);
int right = trval(root.right);
if (left == 2 && right == 2) {
return 0;
}
if (left == 0 || right == 0) {
cnt++;
return 1;
}
if (left == 1 || right == 1) {
return 2;
}
return 0;
}