贪心算法思想_贪心算法实现全局最优的逻辑

基础

贪心没有固定的模板，一般能够从局部最优推出全局最优，且想不出反例，就可以尝试写代码

376. 摆动序列

• 要求删除元素使其达到最大摆动序列
• 局部最优可以推出全局最优
  • 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
  • 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
    
• 贪心思想：让峰值尽可能的保持峰值，然后删除单一坡度上的节点

考虑多种特殊情况

• 上下坡存在平坡
  只保留相邻相等元素中最右边的一个，判断条件修改为prediff小于等于0或大于等于0；
  prediff记录的是上一个节点到当前节点的方向，curdiff记录的是当前节点到下个节点的方向
  
• 仅存在首尾元素
  默认设置prediff=0，默认设置res=1，遍历到倒数第二个元素就可以
  
• 单调坡存在平坡
  这种情况下，按照之前的判断逻辑会把334这里的摆动也算进去，但是这里是单调递增的情况，不应该被算进去；
  避免这种情况，在存在摆动时，才更新$prediff=curdiff$；
  因此334这里的$prediff=1$，是在12这里记录的。
  

class Solution {
    public int wiggleMaxLength(int[] nums) {
        //单个元素的情况
        if(nums.length == 1)    return 1;
        int prediff = 0;
        int curdiff;
        //只有首尾元素的情况
        int res = 1;
        for(int i = 0; i < nums.length - 1; i++){
            curdiff = nums[i+1] - nums[i];
            //上下坡中存在平坡
            if(prediff <= 0 && curdiff > 0 || prediff >= 0 && curdiff < 0){
                res++;
                //单调坡中存在平坡
                prediff = curdiff;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

53. 最大子数组和

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = 0;
        int max = -10001;
        for(int i = 0; i < nums.length; i++){
            res += nums[i];
            max = Math.max(res,max);
            if(res < 0) res = 0;
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

122. 买卖股票的最佳时机 II

最终利润是可以分解的，把利润分解为每天为单位的维度
局部最优：收集每天的正利润，全局最优：求得最大利润

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i = 0; i < prices.length - 1; i++){
            int profit = prices[i+1] - prices[i] ;
            if(profit > 0)
                res+= profit;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

714. 买卖股票的最佳时机含手续费

本题计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。此时无非就是要找到两个点，买入日期，和卖出日期。

贪心理解：如果算上手续费还盈利的话，先假装卖了，获得第一次收益，其中减去手续费。然后标记持仓值为免手续费的股票值（股票第一次收益计算了手续费，所以之后真正卖出时就不用算股票手续费）。

• 遍历后面的价格，如果股票继续涨，就再假装卖了，获取收益，其中不包含手续费，然后继续标记它为持仓值。
• 遍历后面的价格，如果股票暴跌，低到 买入的手续费（fee）+股票价格（price[i]）< 持仓股票价格（buy），那么将股票真正卖出，再重新买入当前价格的股票。因为此时卖出再买入，相同仓位，不仅能赚回重新买入时的手续费，下次股票升值时，赚得越多。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        //转换思路，买入时先加上手续费
        int buy = prices[0] + fee;
        int res = 0;
        for(int i = 1; i < prices.length; i++){
            //如果当前价格+手续费小于之前buy的价格，那不如在当前价格购买更划算
            if(prices[i]+fee < buy) buy = prices[i] + fee;
            //如果当前价格高于buy，说明算上手续费，这次买卖也是正收益，但可能不是最大收益
            //先加上这次的收益（计算了手续费），再设置buy为price[i]（以相同价格并且免除手续费买入），若继续增大则可以继续加入到收益中
            if(prices[i] > buy){
                res+=prices[i] - buy;
                buy = prices[i];
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

55. 跳跃游戏

贪心的是最大覆盖范围
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1)    return true;
        int k = nums[0];
        for(int i = 0; i <= k; i++){
            k = Math.max(nums[i] + i, k);
            if(k >= nums.length - 1)    return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11

45. 跳跃游戏 II

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1)    return 0;
        int cur = 0;  //当前覆盖位置
        int next = 0; //下一个覆盖位置
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            next = Math.max(nums[i]+i,next);
            if(i == cur){
            	//当前覆盖位置无法到达终点
                if(cur < nums.length - 1){
                    res++;
                    cur = next;
                    if(next > nums.length - 1) break;
                }else   break;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1005. K 次取反后最大化的数组和

注意按绝对值排序的写法

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        nums = IntStream.of(nums).boxed().sorted((a,b)->Math.abs(b) - Math.abs(a)).mapToInt(Integer::intValue).toArray();
        int sum = 0;
        for(int i = 0; i < nums.length ; i++){
            if( nums[i] < 0 && k > 0){
                nums[i]*=-1;
                k--;
            }
            sum+=nums[i];
        }
        if(k % 2 == 1)  sum-=2 * nums[nums.length - 1];
        return sum;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

134. 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int res = 0;
        for(int i = 0; i <cost.length; i++){
            curSum+= gas[i] - cost[i];
            totalSum+= gas[i] - cost[i];
            if(curSum < 0){
                res = i+1;
                curSum = 0;
            }  
        }
        if(totalSum < 0)    return -1;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17