理論基礎(chǔ)

貪心算法的本質(zhì)是由局部最優(yōu)推到全局最優(yōu)，沒有特定的套路

455.分發(fā)餅干

455. 分發(fā)餅干 - 力扣（LeetCode）
本題考慮將大餅干喂給胃口大的孩子，遍歷孩子胃口的數(shù)組，用大餅干依次喂，直到滿足條件，再移動(dòng)餅干的位置

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        //要遍歷小孩胃口，不合適就下一個(gè)，因?yàn)橐獜拇蟮叫“扬灨煞滞?        for (int i = g.length - 1; i >= 0; i--) {
            //這里用if就可以，不需要用while
            if (start >= 0 && s[start] >= g[i]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

376. 擺動(dòng)序列

376. 擺動(dòng)序列 - 力扣（LeetCode）
本題局部最優(yōu)是“刪除”單調(diào)序列上中間的值，由此可以推出全局最優(yōu)最長擺動(dòng)子序列的長度。要注意有平坡的情況，要么都在curDiff加上=，要么在preDiff加上=

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

53. 最大子序和

53. 最大子數(shù)組和 - 力扣（LeetCode）
本題主要是如何找到子數(shù)組的起始位置，當(dāng)前面數(shù)組和為負(fù)數(shù)并且下一個(gè)數(shù)為正數(shù)時(shí)，那么就將起始位置設(shè)置為這個(gè)正數(shù)，然后再持續(xù)計(jì)算比較子數(shù)組總和

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            maxSum = Math.max(sum, maxSum);
            //sum小于0時(shí)，就重新設(shè)置起始位置
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
    }
}