代码随想录算法训练营第三十一天 | 分发饼干、摆动序列、最大子数组和

分发饼干

题目要求尽量让更多的孩子吃的上饼干，所以饼干尽量不浪费，也就是说胃口小的吃小饼干，胃口大的吃大饼干。所以需要对饼干大小和孩子的胃口排序，正序排列，倒序排列都可以。

// 从小到大排序
class Solution {
    // g: 孩子胃口, s: 饼干尺寸
    public int findContentChildren(int[] g, int[] s) {
        // 从小到大排序
        Arrays.sort(g);
        Arrays.sort(s);

        // 用于遍历孩子胃口
        int i = 0;
        // 用于遍历饼干尺寸
        int j = 0;
        int count = 0;
        // 遍历孩子的胃口和饼干尺寸
        while (i < g.length && j < s.length) {
            // 如果这块饼干的尺寸满足孩子的胃口，则分给他
            if (s[j] >= g[i]) {
                // 遍历下一个孩子
                i++;
                // 遍历下一块饼干
                j++;
                // 满足数 +1
                count++;
            } else {
                // 不满足孩子胃口，则孩子等一等，遍历下一个饼干
                // 因为 g[i] 已经是当前胃口最小的孩子了，吃 s[j] 仍吃不饱，那就试试下一个饼干
                j++;
            }
        }

        return count;
    }
}

// 从大到小
var findContentChildren = function(g, s) {
    // 还是 JS 的排序好写
    g.sort((a, b) => b - a);
    s.sort((a, b) => b - a);

    // 用于遍历孩子胃口
    let i = 0;
    // 用于遍历饼干尺寸
    let j = 0;
    let count = 0;

    // 遍历孩子的胃口和饼干尺寸
    while (i < g.length && j < s.length) {
        // 如果这块饼干的尺寸满足孩子的胃口，则分给他
        if (s[j] >= g[i]) {
            // 遍历下一个孩子
            i++;
            // 遍历下一块饼干
            j++;
            // 满足数 +1
            count++;
        } else {
            // 不满足孩子胃口，则饼干等一等，遍历下一个孩子
            // 因为 s[j] 已经是当前最大的饼干了，还不满足 g[i] 的话，那别让他吃了
            i++;
        }
    }

    return count;
};

摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        int prevDiff = nums[1] - nums[0];
        int count = prevDiff == 0 ? 1 : 2;

        for (int i = 2; i < nums.length; i++) {
            int currDiff = nums[i] - nums[i - 1];
            if ((prevDiff <= 0 && currDiff > 0) || (prevDiff >= 0 && currDiff < 0)) {
                count++;
                prevDiff = currDiff;
            }
        }

        return count;
    }
}

最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;

        for (int num : nums) {
            sum += num;
            if (sum > max) {
                max = sum;
            }
            // 如果连续和已经小于 0 了，那么再往后累加都是在 “减小”
            // 所以重新计算累加和
            if (sum < 0) {
                sum = 0;
            }
        }

        return max;
    }
}