代码随想录算法训练营第二十七天|455分发饼干、376摆动序列、53最大子序和

day27 贪心算法 part01

贪心算法没有什么规律可言, 没有思路就立刻看题解。

1. 455分发饼干

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

先将饼干数组和小孩数组排序，然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int sum = 0;
        for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口
            if (index >= 0 && s[index] >= g[i]) { // 遍历饼干
                sum++;
                index--;
            }
        }
        return sum;
    }
};

2. 376摆动序列

• 摆动序列的定义

  1. 什么是摆动序列？
     • 一组数字的差值必须严格交替正负。例如，差值是正数、负数、正数……或者是负数、正数、负数……
     • 如果差值重复（比如连续两个正数或负数差值）或为零，就不再是摆动序列。
  2. 子序列的定义：
     • 子序列是通过从原始序列中删除一些元素（可以删除，也可以不删除）获得，且剩下的元素顺序不变。
  3. 目标：
     • 给定一个整数数组 nums，找到其中最长的摆动子序列的长度。

  ---

  解题思路

  1. 我们不需要真的去构造摆动子序列，而是记录摆动序列的长度即可。
  2. 核心逻辑：
     • 用两个变量：
       • up：记录以正差（上升趋势）结束的最长摆动序列长度。
       • down：记录以负差（下降趋势）结束的最长摆动序列长度。
     • 遍历数组时，比较当前元素和前一个元素：
       • 如果当前差值是正的，由于需要是摆动序列，所有是在以负差（下降趋势）结束的最长摆动序列长度上+1，即更新 up = down + 1。
       • 如果当前差值是负的，由于需要是摆动序列，所有是在以正差（上升趋势）结束的最长摆动序列长度上+1，即更新 down = up + 1。
     • 每次更新后，up 和 down 记录的就是以正差或负差结尾的摆动序列的长度。
  3. 总结规律：
     • 正差（上升）时：up 的长度依赖于上一次的 down 长度，因为正差必须接在负差后。
     • 负差（下降）时：down 的长度依赖于上一次的 up 长度，因为负差必须接在正差后。
  4. 最终答案就是 max(up, down)。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;

        // `up` 表示以正差结尾的最长摆动序列长度
        // `down` 表示以负差结尾的最长摆动序列长度
        // up = 1，down = 1（序列最少有一个元素，长度初始为 1）。for循环从第二个元素开始（即i=1开始）
        int up = 1, down = 1;

        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                // 当前差值为正，则以正差结尾的序列长度增加
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                // 当前差值为负，则以负差结尾的序列长度增加
                down = up + 1;
            }
        }

        // 结果为两种最长摆动序列中的最大值
        return max(up, down);
    }
};

3. 53最大子序和

贪心法解题思路

1. 局部最优：
   对于当前遍历到的元素，有两种选择：
   • 要么将当前元素加入之前的子数组中（累加当前元素）。
   • 要么舍弃之前的子数组，重新从当前元素开始。
     局部最优策略就是取两者的较大值。
2. 全局最优：
   在每一步的局部最优中，不断更新一个记录全局最大值的变量。
3. 具体步骤：
   • 初始化 currentSum 为 0，表示当前子数组的和。
   • 初始化 maxSum 为 nums[0]，因为至少有一个元素，最大子数组和不能小于数组中的某个元素。
   • 遍历数组中的每个元素：
     • 如果当前子数组和加上当前元素的值小于当前元素的值，那么直接从当前元素重新开始。
     • 更新全局最大值。

示例

输入数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

执行过程：

• 初始值：maxSum = -2, currentSum = 0
• 遍历：
  • num = -2，currentSum = max(-2, 0 + (-2)) = -2，maxSum = max(-2, -2) = -2
  • num = 1，currentSum = max(1, -2 + 1) = 1，maxSum = max(-2, 1) = 1
  • num = -3，currentSum = max(-3, 1 + (-3)) = -2，maxSum = max(1, -2) = 1
  • num = 4，currentSum = max(4, -2 + 4) = 4，maxSum = max(1, 4) = 4
  • num = -1，currentSum = max(-1, 4 + (-1)) = 3，maxSum = max(4, 3) = 4
  • num = 2，currentSum = max(2, 3 + 2) = 5，maxSum = max(4, 5) = 5
  • num = 1，currentSum = max(1, 5 + 1) = 6，maxSum = max(5, 6) = 6
  • num = -5，currentSum = max(-5, 6 + (-5)) = 1，maxSum = max(6, 1) = 6
  • num = 4，currentSum = max(4, 1 + 4) = 5，maxSum = max(6, 5) = 6

最终返回：maxSum = 6

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0]; // 全局最大和
        int currentSum = 0;   // 当前子数组和
        for (int num : nums) {
            // 更新当前子数组和：要么从当前元素重新开始，要么继续累加
            currentSum = max(num, currentSum + num);
            // 更新全局最大子数组和
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }
};