算法细节系列（22）：什么时候贪心完！
算法细节系列（22）：什么时候贪心完！
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434762
算法细节系列（22）：什么时候贪心完！
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
- Leetcode 316: Remove Duplicate Letters
- Leetcode 134: Gas Station
- Leetcode 402: Remove K Digits
- Leetcode 045: Jump Game II
- Leetcode 135: Candy
Leetcode 316: Remove Duplicate Letters
唉，贪心这些题，解法真的靠猜，可我咋怎么都猜不中！简直无奈。这是一道删重复字符题，但需要保证删除过后的字符集是the smallest in lexicographical order among all possible results。（也就是说，字符需要维持原先的相对位置）
如：
"bcabc" ---> "abc"先说说我的思路吧，对于字符只有两种选择删or不删，所以先统计所有字符出现的频次，那些只出现一次的字符就不用考虑，而重点考虑那些重复的元素，删or不删。
问题来了，重复的元素出现的位置有多个，到底删哪个呢？因为，只出现一次的字符相对位置是固定的，所以假设我们找到了第一个频次为1的字符，那么在它前面的必然都是出现频次超过两次的元素，如：
"aabczecbzz"
e出现的频次为1，所以e必然留下，那么在前面的元素比e大的可以直接删，所以有：
"aabcecbzz"
那么比e小的元素该如何？肯定全部留下，所以把e后面的元素，且在前面出现的全部置空。如下：
"aabcezz"
这样我们就可以放心递归求解"aabc"而不会在后面出现了，然后继续递归求解e的后面部分。
到这里不知道是否有疑问？咱们继续，如果不存在频次为1的元素该怎么办？很好的问题。
答：没有频次为1的字符也很好办，我们就从原来的数中找最小字母所在的第一个index，然后按照上述方法继续递归。
代码写完发现只能通过212/286个样例，错误样例为：
"bbcaac"
经过一次递归处理得：
"bbcac"
问题出在bb不能直接删除，因为在a之后没有了b！所以a不是一个有效的划分。。。
虽然有上述的试错，但我们已经得到了正确答案，我们要找的划分应该保证左半部分的字符一定会出现在右半部分，那么在众多满足条件的划分中，我们一定寻找字符最小的那个。
所以，新的思路如下：
a. 针对所有元素遍历一遍，针对每个index得到左半部分和右半部分。保证左半部分的元素都能在右半部分找到。
b. 在所有符合情况的index中，找寻字符最小的那个index，这样，我们可以直接删除左半部分，剩下来的就是递归求解右半部分。
如：
a b c a c b
0 1 2 3 4 5
符合步骤a.的下标有 0, 1, 2
符合步骤b.的最小元素就只有下标为0的a了。代码如下：
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
char[] c = s.toCharArray();
int n = c.length;
for (int i = 0; i < n; i++){
cnt[c[i]-'a']++;
}
//字母最小的 index, 删除最小index左边的元素该index右边一定存在
int pos = 0;
for (int i = 0; i < n; i++){
//寻找最小的字符
if (c[i] < c[pos]) pos = i;
//且满足左半部分能在右半部分找到，否则直接break
if(--cnt[c[i]-'a'] == 0) break;
}
return n == 0 ? "" : c[pos] + removeDuplicateLetters(s.substring(pos+1).replaceAll("" + s.charAt(pos), ""));//replaceAll删除右半部分重复的字符c[pos]
}Leetcode 134: Gas Station
这道题，我没弄明白，但思路可以说一下。首先需了解两个事实：
- 性质1：当gas总和小于cost总和时，一定无解。
- 性质2：当gas总和大于cost总和时，一定有解。（如何证明？）
做法如下：
一个sum变量不断累加gasi-costi,即sum += gas[i]-cost[i]，如果sum出现了负，则说明位置0-i都不可能出现可能的位置（由性质1得），当然你可以这么认为，该条件开始时，sum起始一定为正，而加着加着后劲不足，出现了负，汽车是不可能开到i位置的，你更不可能从大于0的位置出发走个循环，因为前面正的sum你都加成负的了，更别说更小的sum了，sum<0只会出现的更早。（还是直接看性质1吧，好理解）
所以，一旦sum<0，更新位置为i+1，且sum置零，重新累加，搜索一个更小的不存在的环，如果这个环最后结束后依旧满足sum>0，且最终构成的大环>0，那么返回位置i+1。
代码如下：
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int sum = 0;
int pos = 0;
int tol = 0;
for (int i = 0; i < n; i++){
sum += gas[i] - cost[i];
//符合性质1的所有位置都不再符合，更新下标为i+1
if (sum < 0){
//虽说小环不符合，但大环不一定不符合，不断累加，全部累加完毕进行判断。
tol += sum;
sum = 0;
pos = i + 1;
}
}
tol += sum;
return tol < 0 ? -1 : pos;
}所以这道题，抽象来看，只有一个知识点，尽可能多的把大环上的一些连续位置给排除了（利用性质1），它排除是连续性的，所以我们可以非常贪心的一下子更新候选下标为pos = i + 1，直到遍历结束，最后判断下整个大环是否符合性质2，符合就返回下标pos。
Leetcode 402: Remove K Digits
思路：
num = "1432219" k = 3
暴力一点的，把每一个位置都删一次，如：
k = 1
432219
132219
142219
...
143221
取最小的num，这就变成了重复子问题，用递归或者迭代都可以，建议迭代，递归容易stack over flow. 针对贪心这货出现的频次相当高
虽然看上去时间复杂度为O(k*n)，不算太高，但字符串之间的大小比较也是开销，所以果断TLE，代码就不列举了。
想象一下，这道题的每个数字大小可以看成崎岖不平的山脉，而删一个数字，对大趋势不会有任何改变。（删除某一位，无非就是把后续的数字全部平移上来）
考虑递增的情况，如果删小的，那么平移过后，比原来的大。如：
1234119
删2得
134119
删3得
124119
显然递增情况删大而不删小。
考虑递减的情况。如果删小，那么平移过后，依然比原来大，不例举了。所以综合上述两个性质，删peek。（删在递增情况下第一次出现递减的那个元素）
其实删的就是山峰，那么多个山峰出现，应该删哪个呢？此处用到了贪心!
删第一个山峰，因为数越靠近左侧，它减小的效果越显著。代码如下：
public String removeKdigits(String num, int k) {
char[] cs = num.toCharArray();
while(k-- != 0){
int i = 1;
while (i < cs.length && cs[i] >= cs[i-1]) i++;
num = num.substring(0, i-1) + num.substring(i);
cs = num.toCharArray();
}
return format(num);
}
private String format(String ans) {
char[] cs = ans.toCharArray();
int i = 0;
while (i < cs.length && cs[i] == '0') i++;
ans = ans.substring(i);
return ans.isEmpty() ? "0" : ans;
}还是一句话，迭代能写，还是用迭代做，递归容易stack over flow，虽然简单一些。
该问题还有更快的版本，前者代码没用到状态记录，而我们知道，在遍历时，适当记录一些信息能够大大加快代码的效率。
思路：
每次都求第一个山峰，所以一旦删除一个元素，前半部分还维持着递增趋势，所以我们删第二个元素时，无非遇到两种情况，依旧递增，那么在原来的基础上应该，继续while循环即可。
如果跟上一个元素相比，出现递减，那么直接删除上一个元素即可。维护该状态记录的我们用stack可以轻松解决，stack中存放不断递增的元素，也就是那个山头。
代码如下：
private String format(String ans) {
char[] cs = ans.toCharArray();
int i = 0;
while (i < cs.length && cs[i] == '0') i++;
ans = ans.substring(i);
return ans.isEmpty() ? "0" : ans;
}
public String removeKdigits(String num, int k) {
char[] cs = num.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < cs.length; i++){
while(k > 0 && !stack.isEmpty() && stack.peek() > cs[i]){
stack.pop();
k--;
}
stack.push(cs[i]);
}
while (k > 0){
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()) sb.append(stack.pop());
return format(sb.reverse().toString());
}上述代码还可以进一步优化，我们自己来实现栈，那么最后就不需要用sb去reverse了，代码如下：
public String removeKdigits(String num, int k) {
char[] cs = num.toCharArray();
char[] stack = new char[num.length()];
int top = -1;
for (int i = 0; i < cs.length; i++){
while (k > 0 && top != -1 && stack[top] > cs[i]){
top--;
k--;
}
stack[++top] = cs[i];
}
while (k-- != 0) top--;
return top == -1 ? "0" : format(new String(stack,0,top+1));
}Leetcode 045: Jump Game II
思路：
还是看范围，根据当前位置，能走的位置有i + nums[i]，在这些位置中找寻能覆盖的范围最大的那个pos，继续迭代寻找，直到抵到最终位置。（BFS，贪心策略，每次寻找范围最大的那个pos，作为下一个起始位置）
代码如下：
public int jump(int[] nums) {
int step = 0, range = 0, now = -1;
while (range < nums.length - 1) {
step++;
int maxRange = 0;
int index = -1;
for (int i = now + 1; i <= range; i++) {
if (i + nums[i] >= maxRange) {
maxRange = i + nums[i];
index = i;
}
}
range = maxRange;
now = index;
}
return step;
}还可以从另外一个角度看问题，比如说，刚开始必然有0+nums[0]，所以说，如果进入位置1时，没有超过这个0+nums[0]，必然不会发生step，而当前i超过了起初的edge，一定在0,i的某个状态进行更新，但无关乎位置，我们只要记录在0,i中，i+nums[i]的最大值即可。
代码如下：
public int jump(int[] nums) {
int step = 0, edge = 0, maxRange = 0;
int len = nums.length;
for (int i = 0; i < len; i++){
if (i > edge){
step ++;
edge = maxRange;
//每次当作一个子问题看
maxRange = 0;
}
maxRange = Math.max(maxRange, i + nums[i]);
}
return step;
}这几道题有一些明显的特点，每次进入迭代状态更新时，都变成了原问题的子问题，这估计是贪心的一个比较有趣的现象。或者说，我们只要每次能找到状态更新的子问题就能把问题给解决了？
Leetcode 135: Candy
思路：
这道题还是找上升和下降的趋势，只不过这次上升和下降的趋势是独立的，所以我们可以分两次遍历来简化该问题。初始所有糖果为1，遇到递增的ratings，糖果在原来的基础上+1.反之一样。
初始化：
ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
正向traverse
ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 2, 1, 1, 2, 3, 4, 1, 1, 1, 2, 1]
反向traverse
ratings: [5, 6, 2, 2, 4, 8, 9, 5, 4, 0, 5, 1]
candies: [1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 2, 1]代码如下：
public int candy(int[] ratings) {
int len = ratings.length;
int[] candies = new int[len];
Arrays.fill(candies, 1);
for (int i = 0; i < len; i++){
if (i == 0) continue;
if (ratings[i] > ratings[i-1]){
candies[i] = candies[i-1] + 1;
}
}
for (int i = len - 1; i >= 0; i--){
if (i == len -1) continue;
if (ratings[i] > ratings[i+1]){
candies[i] = Math.max(candies[i+1] + 1,candies[i]);
}
}
int sum = 0;
for (int candy : candies){
sum += candy;
}
return sum;
}