No.1

题目

思路

局部最优原则，大饼干优先满足大胃口孩子
倒序遍历数组

代码

public int findContentChildren(int[] g, int[] s) {  
    Arrays.sort(g);  
    Arrays.sort(s);  
  
    int satisfied = 0;  
    int s_index = s.length - 1;  
    for(int g_index = g.length - 1; g_index >= 0 && s_index >= 0; g_index--) {  
        int cookieSize = s[s_index];  
        if (cookieSize >= g[g_index]) {  
            satisfied++;  
            s_index--;  
        }  
    }  
  
    return satisfied;  
}

No.2

题目

摆动序列

思路

贪心算法
数字在序列中的大小，类比为坡的高度
分情况讨论
- 上下坡中间有平坡
- 单调坡中间有平坡
其实没有感觉到用了贪心，可能是我理解不深入

代码

public int wiggleMaxLength(int[] nums) {  
    if (nums.length == 1)  
        return 1;  
    if (nums.length == 2 && nums[0] != nums[1])  
        return 2;  
  
    int preDiff = 0;  
    int curDiff = 0;  
    int result = 1;  
    for (int i = 0; i + 1 < nums.length; i++) {  
        if (nums[i] == nums[i + 1])  
            continue;  
        curDiff = nums[i + 1] - nums[i];  
        if (preDiff >= 0 && curDiff < 0 || preDiff <= 0 && curDiff > 0)  
            result++;  
        preDiff = curDiff;  
    }  
  
    return result;  
}

No.3

题目

最大子数组和

思路

贪心法核心是局部最优构成全局最优
怎么贪？负数只会拉低总和，累计总和为负时，当前连续序列就得选择新的起点

代码

public int maxSubArray(int[] nums) {  
    int max = Integer.MIN_VALUE;  
    int subSum = 0;  
    for (int i = 0; i < nums.length; i++) {  
        subSum += nums[i];  
        if (subSum < 0) {  
            max = Math.max(subSum, max);  
            subSum = 0;  
            continue;  
        }  
        max = Math.max(subSum, max);  
    }  
  
    return max;  
}