贪心算法理论基础

题目分类大纲如下：

 

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

分发饼干

455. 分发饼干 - 力扣（LeetCode）

将尺寸大的饼干尽量分给胃口大的孩子这样以达到尺寸的最大利用好

   /**
     * @param g 孩子胃口数组
     * @param s 饼干尺寸数组
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        //先对数组进行排序确保胃口大的孩子在后面，尺寸大的饼干在后面
        Arrays.sort(g);
        Arrays.sort(s);
        int result = 0;//存储答案
        int index = s.length - 1;//饼干数组的下标
        for (int i = g.length - 1; i >= 0; i--) {//遍历孩子
            if (index >= 0 && s[index] >= g[i]) {
                result++;
                index--;
            }
        }
        return result;
    }

摆动序列

376. 摆动序列 - 力扣（LeetCode）

在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

这是我们思考本题的一个大体思路，但本题要考虑三种情况：

情况一：上下坡中有平坡

 

 

在图中，当 i 指向第一个 2 的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个 2 的时候 prediff = 0 && curdiff < 0。

如果我们采用，删左面三个 2 的规则，那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。

情况二：数组首尾两端

因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。

这里我们可以写死，就是 如果只有两个元素，且元素不同，那么结果为 2。

情况三：单调坡中有平坡我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。

完整代码：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int res=1;
         int pre=0;
         int cur=0;
         if(nums.length<=1){
             return nums.length;
         }
         for (int i = 0; i <nums.length-1 ; i++) {
             cur=nums[i+1]-nums[i];
            if((cur>0&&pre<=0)||(cur<0&&pre>=0)){
                res++;
                pre=cur;
            }

        }
    return res;
    }
}

最大子序和

53. 最大子数组和 - 力扣（LeetCode）

如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

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