455. 分发饼干

image.png

思路1
从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

  1. class Solution {
  2.     public int findContentChildren(int[] g, int[] s) {
  3.         Arrays.sort(g);
  4.         Arrays.sort(s);
  5.         int start = s.length-1;//饼干的下标，也是倒的
  6.         int count = 0;//统计的数量
  7.         for (int i = g.length-1; i >=0; i--){//从后向前遍历小孩数组，最大的饼干给胃口大的小孩
  8.             if (start >= 0 && g[i] <= s[start]){
  9.                 start--;
  10.                 count++;
  11.             }
  12.         }
  13.         return count;
  14.     }
  15. }

思路2
小饼干先喂饱小胃口

class Solution {
    // 思路1：优先考虑饼干，小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

376. 摆动序列

https://www.programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html#%E6%80%9D%E8%B7%AF1-%E8%B4%AA%E5%BF%83%E8%A7%A3%E6%B3%95
image.png

思路1（贪心算法）

image.png局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
image.png

class Solution {
   public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值//初始时默认前面有一个
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.length - 1; i++) {
            curDiff = nums[i+1] - nums[i];
            if ((curDiff > 0 && preDiff <= 0 )||(preDiff >= 0 && curDiff < 0)){
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
}

思路2（动态规划）

待补。。。

53. 最大子数组和

image.png
贪心贪的是哪里呢？
如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
贪心 - 图7

class Solution {
    public int maxSubArray(int[] nums) {
        int count = 0;
        int result =Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            if (count > result){// 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count < 0) count = 0;// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
}

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

https://www.programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
image.png
image.png

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i-1],0);
        }
        return result;
    }
}

55. 跳跃游戏

https://labuladong.github.io/algo/3/27/102/
image.png
这道题表面上不是求最值，但是可以改一改：
请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回 true，否则返回 false。
所以解题关键在于求出能够跳到的最远距离。

boolean canJump(int[] nums) {
    int n = nums.length;
    int farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = Math.max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) {
            return false;
        }
    }
    return farthest >= n - 1;
}

45. 跳跃游戏 II

image.png

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

image.png