贪心算法:理论基础 分发饼干 摆动序列 最大子序和

2023-12-15 13:37:27

理论基础?

  • 什么是贪心算法?
    • 贪心的本质是选择每一阶段的局部最优,从而达到全局最优
  • 什么时候用贪心算法?
    • 贪心算法并没有固定的套路。唯一的难点就是如何通过局部最优,推出整体最优。
  • 如何验证可不可以用贪心算法?
    • 最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧
  • 贪心算法一般解题步骤(比较理论化,实用性不强)
    • 将问题分解为若干个子问题
    • 找出适合的贪心策略
    • 求解每一个子问题的最优解
    • 将局部最优解堆叠成全局最优解


455.分发饼干

  • 思路:
    • 如果用最大的饼干来喂胃口最小的孩子,势必会造成饼干尺寸的浪费。所以为了满足更多的小孩,思路应该是尽量用大的饼干来满足胃口大的孩子从后向前遍历小孩数组,尺寸大的饼干优先满足胃口大的孩子,并统计满足小孩数量(或小饼干先喂饱小胃口)。
    • 局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)
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 index = s.size() - 1;//遍历饼干时的下标
        for(int i = g.size() - 1; i >= 0; i--) {//遍历孩子的胃口
            if(index >= 0 && s[index] >= g[i]) {//遍历饼干
                count++;
                index--;
            }
        }
        return count;
    }
};


376.?摆动序列

  • 思路:
    • 大体思路:让峰值尽可能的保持峰值,然后删除单一坡度上的节点
      • 局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值
      • 整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列
    • 考虑三种情况(prediff:与前一个数的差,curdiff:与后一个数的差):
      • 情况一:上下坡中有平坡
        • 数组[1,2,2,2,2,1]的摇摆序列长度为3,也就是[1,2,1],那么应该取哪一个2呢?不妨统一规则,保留最后一个
        • 当遍历到第一个2时,prediff > 0 && curdiff = 0;当遍历到最后一个2时,prediff = 0 && curdiff <?0,此时要记录一个峰值。
      • 情况二:数组首尾两端
        • ???????数组[2,5],在计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i])的时候,至少需要三个数字才能计算,而只有两个不同数字的无法这样计算,但显然摇摆序列长度为2。
        • 如果不只有两个元素,我们在判断首尾元素时依旧无法使用上述方法。不妨假设数组最前面还有一个数字,与第一个数字相同,此时prediff = 0,就可以用情况一来判断。而默认最后有一个峰值(统计变量初始化为1)。
      • 情况三:单调坡中有平坡
        • ???????数组[1,2,2,2,3,4],根据情况一,遍历到最后一个2时,prediff = 0,curdiff > 0,会记录一个峰值,这样计算出结果会是3,但实际上摇摆序列长度应该为2。
        • 出错的原因是因为实时更新了 prediff,只需要在 这个坡度 摆动变化的时候,更新 prediff 就行,这样 prediff 在 单调区间有平坡的时候 就不会发生变化,造成我们的误判。

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int res = 1;//默认最后一个元素为一个峰值,记录峰值个数
        int prediff = 0;//与前一元素的差
        int curdiff = 0;//与后一元素的差
        for(int i = 0; i < nums.size() - 1; i++) {//因为默认最后一个为峰值,所以i < nums.size() - 1
            curdiff = nums[i + 1] - nums[i];
            //出现峰值
            if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {
                res++;
                prediff = curdiff;//只在统计到峰值的时候更新prediff
            }
        }
        return res;
    }
};


53.?最大子序和?

  • 思路:
    • 如果前面的和为负数,不管什么数加上负数,总和肯定会变小,因此使用贪心算法时,会直接舍弃前面和为负数的这段,直接从下一个元素开始重新计算连续子序列和
    • 全局最优:选取最大“连续和”
    • 局部最优的情况下,并记录最大的“连续和”,可以推出全局最优
    • 本质上就是不断调整子序列区间求和,区间的终止位置,就是如果当前总和取到最大值时,及时用result变量记录下来。
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            //取区间累计的最大值(相当于不断确定最大子序终止位置)
            res = sum > res ? sum : res;
            if(sum <= 0) sum = 0;//重置最大子序起始位置,因为遇到负数一定是拉低总和
        }
        return res;
    }
};


总结

最好举反例,举不出反例时就可以考虑使用贪心算法

参考链接

代码随想录:理论基础? 分发饼干? 摆动序列? 最大子序和

文章来源:https://blog.csdn.net/m0_59425585/article/details/134925122
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。