主要思想：

  • 由局部最优推导全局最优，并且举不出明显的反例
  • 需要自己思考，没有必要进行数学证明。

1、饼干分发

优先用大饼喂大胃

  1.     // 思路2：优先考虑胃口，先喂饱大胃口
  2.     public int findContentChildren(int[] g, int[] s) {
  3.         Arrays.sort(g);
  4.         Arrays.sort(s);
  5.         int count = 0;
  6.         int start = s.length - 1;
  7.         // 遍历胃口
  8.         for (int index = g.length - 1; index >= 0; index--) {
  9.             //保证别报错
  10.             // g[index] <= s[start] 大饼干优先满足大胃口。
  11.             if(start >= 0 && g[index] <= s[start]) {
  12.                 start--;
  13.                 count++;
  14.             }
  15.         }
  16.         return count;
  17.     }

小饼干优先满足小胃口

2、最长子序列

本题中的局部思想，是通过简单求和，如果和大于result，则对result进行赋值，否则将局部和赋值为0，类似与左右值的变化

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if (nums.length == 1){
  4.             return nums[0];
  5.         }
  6.         int result =  Integer.MIN_VALUE;//记录min值，用于做比较
  7.         int count = 0;
  8.         for (int i = 0; i < nums.length; i++) {
  9.             count = count + nums[i]; //局部和
  10.             if (count > result) {
  11.                 result = count; //将最终结果和局部和进行比较
  12.             }
  13.             if (count <= 0) {
  14.                 count = 0;  //索引下标不变，变得是总和，其实也想到与改变下标
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. }

3、股票最大值

主要思想参考上题，赋值两个变量，分别记录局部最优和全局最优，在局部最优逻辑中，用两天的值进行比较

  1.     public int maxProfit(int[] prices) {
  2.         if (prices.length == 0) {
  3.             return 0;
  4.         }
  5.         int sum = 0; //综合
  6.         int count = 0;  //局部和
  7.         for (int i = 1; i < prices.length; i++) {
  8.             if (prices[i - 1] > prices[i]) {
  9.                 count = 0;
  10.             } else {
  11.                 count += (prices[i] - prices[i - 1]);
  12.             }
  13.             sum += count;
  14.         }
  15.         return sum;
  16.     }

优化版

  1.    public int maxProfit(int[] prices) {
  2.         int result = 0;
  3.         for (int i = 1; i < prices.length; i++) {
  4.             result += Math.max(prices[i] - prices[i - 1], 0);
  5.         }
  6.         return result;
  7.     }

4、跳跃游戏

从第一步开始跳，当前位置能到的最远距离：nums[i] + i ，再用converge = Math.max(converge, nums[i] + i) 与目标位置进行判断，如果能到达则返回true

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         if (nums.length==1) return true;
  4.         int converge = 0;
  5.         for (int i = 0; i <= converge; i++) { //设定范围，第一步可以直接走
  6.             converge = Math.max(converge, nums[i] + i);  //后续取步数最大值
  7.             if (converge >= nums.length - 1) {
  8.                 return true;
  9.             }
  10.         }
  11.         return false;
  12.     }
  13. }

5、K 次取反后最大化的数组和

思路：需要对数字取反，由于必须要取反所以结果有两种情况

  • 增大：取绝对值大的负数
  • 减小：取绝对值小的正数

按照这个思路，需要首先对数组进行按绝对值排序

  1.     public int largestSumAfterKNegations(int[] nums, int K) {
  2.         // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
  3.     nums = IntStream.of(nums)
  4.              .boxed()
  5.              .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
  6.              .mapToInt(Integer::intValue).toArray();
  7.     int len = nums.length;        
  8.     for (int i = 0; i < len; i++) {
  9.         //从前向后遍历，遇到负数将其变为正数，同时K--
  10.         if (nums[i] < 0 && K > 0) {
  11.             nums[i] = -nums[i];
  12.             K--;
  13.         }
  14.     }
  15.     // 如果K还大于0，那么反复转变数值最小的元素，将K用完
  16.     // 可以使影响变得最小
  17.     if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
  18.     return Arrays.stream(nums).sum();
  20.     }

6、摆动序列

力扣

  1.     public int wiggleMaxLength(int[] nums) {
  2.         int size = nums.length;
  3.         if (size == 1) {
  4.             return 1;
  5.         }
  6.         int preDiff = 0; //初始值设置为0，可以理解为增加一个首节点一致的节点
  7.         int curDiff = 0; //这个初始值没有作用
  8.         int res = 0;
  9.         for (int i = 0; i < size-1; i++) {
  10.             curDiff = nums[i + 1] - nums[i]; //取下一个数字和当前值的差值
  11.             if (preDiff >= 0 && curDiff < 0 || preDiff <= 0 && curDiff > 0) {
  12.                 res++;
  13.                 preDiff = curDiff; //只有方向变的时候才对pre进行赋值，可以防止单调升的情况
  14.             }
  15.         }
  16.         return res+1;
  17.     }

类似于这种容易让人容易懵的题，都可以先画个曲线图，然后根据题意想一下主要思路，再考虑边界值的处理，最后考虑一些特殊情况。

7、最大子数组和

力扣

从局部上来说就是

  • 当前面的数字之和小于0时，那么与后面的数字相加实际上是有拖累的
  • 因此当前面数字之和小于0时，结果不妨从当前数字算起
  1.     public int maxSubArray(int[] nums) {
  2.         int max = Integer.MIN_VALUE;
  3.         int sum = 0;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             if (sum < 0) {  
  6.                 sum = 0; //数字之和被拖累，sum从0开始
  7.             }
  8.             sum += nums[i];
  9.             max = Math.max(sum, max);
  10.         }
  11.         return max;
  12.     }

8、加油站

力扣

与第7题类似，这也是绝不总和小于0，会拖累结果 image.png可以 每个加油站的剩余量rest[i]为gas[i] - cost[i]。 i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

  1.     public int canCompleteCircuit(int[] gas, int[] cost) {
  2.         int curSum = 0;
  3.         int totalSum = 0;
  4.         int res = 0;
  5.         for (int i = 0; i < gas.length; i++) {
  6.             curSum += gas[i] - cost[i];
  7.             totalSum += gas[i] - cost[i];
  8.             if (curSum < 0) { //小于0时，说明从当前加油站之前的所有车站都不能满足条件，因此需要从下一站开始
  9.                 //累计和设为0
  10.                 curSum = 0;
  11.                 //结果指向下一个值
  12.                 res = (i + 1) % gas.length;
  13.             }
  14.         }
  15.         if (totalSum < 0) {
  16.             return -1;
  17.         }
  18.         return res;
  20.     }