贪心算法基础
贪心算法是一种在求解问题时采取逐步构建解决方案的算法策略。它通过在每一步选择在当前看来最优的选择（即“贪心”选择），希望通过局部最优解的累积得到全局最优解。
贪心算法的核心思想
- 局部最优：每一步都选择在当前状态下最优的选择，不考虑后续步骤可能带来的影响。
- 全局最优：通过一系列的局部最优选择，希望能最终得到问题的全局最优解。
贪心算法的例子
- 活动选择问题：选择参加的活动，使得不冲突的活动数量最多。贪心策略是每次选择结束最早的活动。
- 背包问题（简单版）：给定一组物品，每个物品有价值和重量，选择一些物品装入背包，贪心策略可以是每次选择单位价值最高的物品。
- 哈夫曼编码：用于压缩数据，贪心策略是每次选择频率最低的两个节点合并。
贪心算法的步骤
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
什么时候用？没有什么套路，就是常识性推导加举反例。
455.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子
i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j]。如果s[j] >= g[i]，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。示例 1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。示例 2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2。
思路
局部最优就是大饼干喂给胃口大的小孩（也可以反过来小饼干为给胃口小的先），依次类推，做到全局最优尽可能喂饱尽量多的小孩。
所以先给两个数组排序。最外层的for循环依次遍历小孩的胃口，动态变化的是饼干数组.
代码
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])//局部优先满足胃口大的小孩，如果胃口不满足，胃口会自动遍历下一个，而饼干只有满足了才往前遍历，所以这两个顺序不能变
{
index--;
count++;
}
}
return count;
}
};基本解题思路就是想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心。
376.摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2
思路（贪心解法）
dp还没学。大概就是遍历过程中遇到摆动（峰值）了就count++，这样就不用处理删除元素更复杂的问题了。
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
有三种情况需要处理，本题细节较多。
1.上下坡有平坡
我们统一记录最右边那个2，所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，为什么这里允许 prediff == 0 ，就是为了 上面我说的这种情况。
2.首尾元素
题目中说了，如果只有两个不同的元素，那摆动序列也是 2。
所以我们可以在首尾元素前或后假装有一个元素。
针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）
3.单调坡有平坡
之所以版本一会出问题，是因为我们实时更新了 prediff。
那么我们应该什么时候更新 prediff 呢？
我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。
代码
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int curDiff=0;//当前一对元素差值
int preDiff=0;//前一对差值
int result=1;//针对题中说当只有两个元素是最长子序列长度为2，所以默认最右边序列有一个峰值
if(nums.size()<=1)return nums.size();
for(int i=0;i<nums.size()-1;i++)
{
curDiff=nums[i+1]-nums[i];
//如果出现峰值
if((preDiff<=0&&curDiff>0)||(preDiff>=0&&curDiff<0))
{
result++;
preDiff=curDiff;//记录前一对差值,注意坡度摆动时才更新pre值，避免单调坡上的平坡问题
}
}
return result;
}
};
53.最大子数组和
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组
是数组中的一个连续部分。示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1] 输出：1示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
思路
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
过程
从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。 终止条件就是比较result和count的数就行了。
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int count=0;
int result=INT32_MIN;//定义一个变量 result，用来存储当前找到的最大子数组和。初始值设为 INT32_MIN（即最小的32位整数），确保任何子数组的和都会比这个值大，从而能正确更新。
for(int i=0;i<nums.size();i++)
{
count+=nums[i];
if(count>result)result=count;//累加结果取最大区间和
if(count<=0)count=0;//重置累加和，因为如果遇到负数相加只会拖累，因该重新记录
}
return result;
}
};总结，这些题看似是简单的，但是想的时候要模拟过程还是有点难的，因为没有固定套路。。哎这两周有点懈怠了啊，有点抗拒写题。加油啊坚持！！已经过半了！！其他学业作业也不用忽视哦！周末补完欠债的。
标签：count,饼干,nums,int,455,53,DAY31,序列,最优 From： https://blog.csdn.net/2301_79865280/article/details/142894652