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

贪心算法

什么是贪心

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

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。

贪心算法固定套路？

贪心没有套路，说白了就是常识性推导加上举反例。

参考链接：https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

455.分发饼干

题目链接：455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

文章讲解/视频讲解：https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路

首先将孩子的胃口值数组vector<int> g和饼干数组vector<int> s排序，然后采用贪心的思路解决。

找局部最优策略就是把正好等于或者正好大一点的饼干给对应的孩子。把孩子的胃口和饼干大小排序，从小到大，先满足胃口小的孩子的要求，如果当前的饼干$j$满足不了当前的孩子$i$，那么这块饼干肯定满足不了孩子$i+1$以及之后的孩子。

C++实现

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int count = 0;
        int j = 0;
        for(int i = 0;i<g.size();i++){
            while(j < s.size() && g[i] > s[j]) j++;
            if(j < s.size()){
                j++;
                count++;
            }
        }
        return count;
    }
};

376. 摆动序列

题目链接：376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

文章讲解/视频讲解：https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

思路

用贪心的策略来解决。

从后往前找最长的子序列，然后对于当前下标$i$，在$[i+1,nums.size()?1]$范围内寻找它倒序的上一个元素$j$，这个元素需要和$i$满足摆动序列的性质，且后续的序列长度最长。

C++实现

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int length1 = getLength(nums, true);
        int length2 = getLength(nums, false);
        return max(length1, length2);
    }

    int getLength(const vector<int>& nums, bool ascendingOrder){
        int maxCount = 0;

        vector<int> maxCounts(nums.size(), 1);
        vector<bool> turns(nums.size(), false);
        turns[nums.size() - 1] = ascendingOrder;

        for(int i = nums.size() - 1;i>=0;i--){

            int maxj = -1;
            bool turnj = false;

            for(int j = i + 1;j<nums.size();j++){
                if((turns[j] && nums[i] < nums[j]) || (!turns[j] && nums[i] > nums[j])){
                    if(maxj == -1 || maxCounts[j] > maxCounts[maxj]){
                        maxj = j;
                        turnj = turns[j];
                    }
                }
            }
            if(maxj != -1){
                maxCounts[i] = maxCounts[maxj] + 1;
                turns[i] = !turnj;
            }
        }

        for(int i = 0;i<maxCounts.size();i++){
            maxCount = max(maxCount, maxCounts[i]);
        }

        return maxCount;
    }
};

53. 最大子序和

题目链接：53. 最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

文章讲解/视频讲解：https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

思路

构建一个数组vector<int> sums，存储每个下标$i$，以$i$为终点的最大连续子数组和。

局部最优的迭代过程：对于当前下标$i$，如果sums[i-1]大于零，那么sums[i] = sums[i-1] + nums[i]，即连接上之前的连续子数组；如果sums[i-1]小于等于零，那么sums[i] = nums[i]，即把前面的元素都丢弃，重新开始一个连续子数组。

C++实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> sums(nums.size(), 0);
        sums[0] = nums[0];

        for(int i = 1;i<nums.size();i++){
            if(sums[i - 1] > 0) sums[i] = sums[i - 1] + nums[i];
            else sums[i] = nums[i];
        }

        int maxSum = numeric_limits<int>::min();
        for(int i = 0;i<sums.size();i++){
            maxSum = max(maxSum, sums[i]);
        }
        return maxSum;
    }
};