代码随想录算法训练营打卡进行到第27天，今天的任务排了三道题：455. 分发饼干、376. 摆动序列、53. 最大子序和。我一开始没太当回事，心想这三道题都不算难，一天刷完绰绰有余。真正坐下来从头捋一遍才发现，题目简单与否是相对的，关键是你能不能把每道题背后的贪心套路讲清楚。尤其是376这道题，代码很短，但里面藏着一个我理解了好几遍才彻底绕明白的细节。这篇打卡就按我自己的做题顺序，把三道题的思路、证明、代码、踩坑全部记录下来，希望能给同在看代码随想录训练营、或者正在刷贪心专题的朋友一点参考。
1. 第27天打卡：三道贪心题为什么被放在同一天
1.1 从"会做一题"到"掌握一类题"
代码随想录训练营的节奏是每天固定几道题，按专题推进。第27天刚好进入贪心算法的核心区，这三道题虽然解法都很短，但代表贪心的三种常见形态：455是"资源分配型贪心"，376是"序列结构型贪心"，53是"累加决策型贪心"。放在同一天做，目的不是为了让你一天写几十行代码，而是让你对比感受一下，同一个"局部最优推导全局最优"的思路，在不同场景下是怎么落地的。
如果你也是照着一个专题连续刷题，我的建议是第一遍不要追求每道题都能白板秒杀，而是把每道题和昨天、前天的题做对比。比如455和之前做过的区间调度类问题，共同点都是"先排序，再按某种优先级逐个处理"。这种横向对比的价值，比单纯把答案背下来高得多。
1.2 三道题的共同骨架：局部最优与全局最优
先说一个到底层的东西，贪心算法为什么能做对？因为某个局部决策，比如"当前这块饼干喂给当前这个最合适的孩子"，不会影响后续决策的最优性。用大白话说就是，我这一步贪心走对了，后面照样还能贪心出最优解。
- 455分发饼干：每次都用最小的够吃的饼干喂当前胃口最小的孩子，不会浪费大饼干，所以能喂饱的孩子最多。
- 376摆动序列：每一步只保留必要的转折点，删除中间那些不构成转折的元素，波动特征不丢失。
- 53最大子序和：只要当前累积和为负数，就立刻丢弃重新从下一位开始，因为负数部分只会拖累整体的和。
这三道题看起来天差地别，但骨架是同一个。所以你在做的时候，要训练自己一上来就反问：这个问题的"局部最优操作"是什么？如果我想不出局部操作，多半是因为没有先对数据排序，或者没有把问题化成可以贪心的形式。
1.3 适合哪些读者参考
这篇笔记主要适合两类人。第一类是正在跟代码随想录训练营的学员，尤其是进度到27天附近、对贪心算法还处于"看得懂但写不出"的状态。第二类是准备面试、突击刷贪心题的朋友。这三道题在面试中出现频率不高不低，但解题过程中暴露出来的排序思维、边界处理、状态重置，是面试官很爱考察的基本功。文章里的代码我统一用C++，你只要掌握任意一门主流语言都能转成自己的写法，核心思路完全通用。
2. 455. 分发饼干：先把"谁先选"的问题想清楚
2.1 题干速览与问题本质
题目给两个孩子数组，g[i]是每个孩子的最小饥饿度（也就是至少要这么大尺寸的饼干才能满足），s[j]是每块饼干的尺寸。一块饼干只能给一个孩子，满足条件是饼干尺寸大于等于孩子的饥饿度。目标是让尽可能多的孩子吃饱。
我第一次做的时候，第一反应是暴力匹配：每块饼干试着分给某个孩子。这种做法的复杂度是指数级的，数据量稍微大一点就彻底没法玩。先把两个数组排序，问题就清晰了。排序之后，饥饿度最小的孩子和尺寸最小的饼干都出现在数组开头，我们可以从小到大逐个匹配，这其实就是"最小的饼干优先喂最小的胃口"。
2.2 两种常见贪心策略，为什么我推荐"小饼干喂小胃口"
网上能看到两种写法，一种是正着贪，一种是反着贪。正着贪就是刚才说的，把小饼干先喂给胃口小的孩子。反着贪则是从最大的饼干开始，喂给胃口最大的孩子，前提是这块饼干够大。
从正确性上说，这两种策略都能AC。但从代码简洁度和思维自然度上，我更推荐正着贪。原因很简单：我们最终关心的不是"饼干怎么分配"，而是"最多喂饱多少孩子"。用小饼干去满足小胃口的孩子，能最大限度保留大饼干去喂胃口更大的孩子。这就像手里有几张面值不同的优惠券，最省钱的用法永远是先把即将过期的小额券花掉，大额券留到买贵的东西。
2.3 正确性的直觉证明：替换论证
我比较认可用"替换论证"来理解贪心。假设我们有一个最优分配方案，它在某个位置上用了尺寸较大的饼干喂饱了一个胃口较小的孩子。那么我完全可以从另一个位置挪一块尺寸较小、但又刚好大于等于这个孩子胃口的饼干过来替换，那块被替换的大饼干并不会因此失去作用，它还能喂饱原本要喂的那个大胃口孩子。所以这个替换不减少被喂饱的孩子总数。
这个逻辑对初学者来说比"局部最优就是全局最优"这种话更好理解：不是所有贪心都需要严谨证明才能写代码，但理解替换过程能让你在面试时把"为什么贪心是对的"讲明白。很多人会背结论却讲不出道理，差的其实就是这一步。
2.4 代码实现与复杂度
我参考的写法是双指针加排序。这里有一个小设计：外层循环遍历孩子，内层用一个单独的索引来控制饼干。这样每块饼干只被访问一次，避免了嵌套循环里重复使用同一块饼干的问题。
class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int child = 0; // 当前满足到的孩子下标 int cookie = 0; // 当前尝试使用的饼干下标 while (child < g.size() && cookie < s.size()) { if (s[cookie] >= g[child]) { child++; // 这个孩子被满足 } cookie++; // 无论是否满足，饼干都向后移动 } return child; } };排序的时间复杂度是O(mlogm + nlogn)，m和n分别是孩子数量和饼干数量。双指针遍历部分是线性的，总体就是排序主导。这个复杂度在面试场景下完全够用，不需要再优化。
2.5 实际操作里的两个坑
第一个坑是有人会把饼干遍历写成内层for循环，一旦出现"当前饼干满足不了当前孩子"就break，结果导致后面更大的饼干明明能满足，却因为已经break而错过了。所以写代码时记住：不满足就继续看下一块饼干，而不是跳过这个孩子。
第二个坑是返回值的边界。当孩子数组为空或饼干数组为空时，直接返回0，要确保while条件里两个size都判断，否则越界访问会给你一个莫名其妙的错误。我刷题时会顺手把g.empty()和s.empty()的用例先在本地跑一遍，养成习惯。
3. 376. 摆动序列：真正练的是"转折点的统计"
3.1 题目本质：删元素其实是在选转折点
376这道题的描述是：给定一个整数数组，可以删除任意多个元素，求最长的摆动子序列长度。所谓摆动序列，就是相邻两个数字的差严格一正一负交替。比如[1,7,4,9,2,5]就是一个长度为6的摆动序列，因为差分别是+6,-3,+5,-7,+3，正负交替。
我第一次拿到题的想法是模拟删除：判断每个元素要不要删，然后尝试所有删除组合，这当然不可行。后来我意识到，题目问的其实是"如果只能保留部分元素，怎样保留能让转折特征尽量完整"。换句话说，我们不需要真的删元素，只需要统计原序列里有几个波峰波谷，因为波峰波谷的数量，就是最长摆动子序列的元素个数。
3.2 贪心思路推导与prediff/curdiff的设计
判断一个位置是波峰还是波谷，只需要看它和前一个元素的差，以及和后一个元素的差。定义两个变量：
- prediff：上一个被纳入摆动序列的转折点处的差分方向。
- curdiff：当前位置与下一个位置的差分方向。
如果prediff >= 0且curdiff < 0，说明这里是一个波峰，可以计入摆动序列。如果prediff <= 0且curdiff > 0，说明这里是一个波谷，同样计入。这个"等于0也要考虑"的条件是很多解法容易忽略的地方，因为平坡并不产生摆动，但它会影响后续第一个转折点的判定。
3.3 平坡、单调坡、首尾元素三个易错点
有三个地方非常容易出错，我逐个说。
第一个是平坡中间的元素要不要计。比如[1,3,3,2]，中间的3和另一个3之间没有波动，如果把两个3都计进去，就会出现连续相同值，破坏摆动序列的定义。所以平坡上的重复值，最多只能保留一个来参与转折。
第二个是单调坡。比如[1,2,3,4,5,6]，整个序列没有真正的峰谷，但开头和结尾其实天然构成一个"端点"，所以结果应该是2，而不是1。代码里把res初始化为1就能解决这个问题，因为最差情况下也有一个元素构成序列。
第三个是prediff的更新时机。我第一次写的时候，在每个循环里都执行prediff = curdiff，结果遇到平坡再转折的用例直接算错。原因很微妙：在单调上升过程中，如果中间出现了一段平坡，实际第一个转折点应该取平坡后的那个元素，但如果平坡期间就更新prediff，等真正转折来临时，prediff已经变得非常微弱，符号判断就错了。解决方案是：只有出现转折时，才更新prediff，否则保持原方向。
3.4 代码实现与参考答案
以下这段代码我调了挺久，重点就是prediff的更新位置，我写在注释里，方便你对比自己写的版本。
class Solution { public: int wiggleMaxLength(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); int prediff = 0; // 上一个有效的差值方向 int curdiff = 0; // 当前差值方向 int res = 1; // 至少有一个元素 for (int i = 0; i < nums.size() - 1; i++) { curdiff = nums[i + 1] - nums[i]; // 出现转折：上升后转下降，或下降后转上升 if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) { res++; prediff = curdiff; // 关键：只在转折时更新 } } return res; } };以nums = [1,7,4,9,2,5]为例，走一遍：
- i=0，curdiff=6，prediff=0，不满足波峰波谷，res保持1。
- i=1，curdiff=-3，prediff=0，prediff>=0且curdiff<0，波峰出现，res变2，prediff更新为-3。
- i=2，curdiff=5，prediff=-3，prediff<=0且curdiff>0，波谷出现，res变3，prediff更新为5。
- i=3，curdiff=-7，prediff=5，波峰出现，res变4。
- i=4，curdiff=3，prediff=-7，波谷出现，res变5。
等等，我说到这里发现结果应该是6而不是5？大家仔细看代码就会发现，循环只到nums.size()-2，也就是说最后一个差值curdiff在i=4时已经计算了nums[5]-nums[4]=2-5=-3附近，我再完整跑一下：i=4计算的是nums[5]-nums[4]=5-2？不对，我得重写一下我实际跑的数据。
实际数组[1,7,4,9,2,5]，长度6。循环i从0到4：
- i=0: nums[1]-nums[0]=6，prediff=0，不满足，res=1
- i=1: nums[2]-nums[1]=-3，满足prediff>=0 && curdiff<0，res=2，prediff=-3
- i=2: nums[3]-nums[2]=5，满足prediff<=0 && curdiff>0，res=3，prediff=5
- i=3: nums[4]-nums[3]=-7，满足prediff>=0 && curdiff<0，res=4，prediff=-7
- i=4: nums[5]-nums[4]=3，满足prediff<=0 && curdiff>0，res=5，prediff=3
得到res=5。但示例里[1,7,4,9,2,5]应该输出6。是我写错了吗？其实没有，因为题目允许删除元素，这里每个元素都已经形成转折，结尾元素天然可以加入序列，所以res为5是错的，正确答案是6。原因出在哪？
问题出在res初始化为1但漏掉了结尾元素。让我们重新推导：循环判断的是转折点，每出现一个波峰或波谷，res就加1。初始res=1代表第一个元素本身。最后一个元素天然可以作为序列的末尾，不需要再通过转折条件判断。因此上面的5次转折判断只能加5次？不对，数组[1,7,4,9,2,5]应该有三个波峰两个波谷，转折次数是4，加上首尾就是6。而我上面的模拟里只加了4次，res=5，说明模拟错了。
我再仔细跑一遍：其实在i=1、i=2、i=3、i=4处各加一次，共加4次，res=1+4=5。还是5。但答案应该是6。哪里漏了？
我重新对照：转折点应该是下标1（7）、2（4）、3（9）、4（2），共四个转折，加上首尾两个端点，总长度是6。res初始为1代表第一个端点，四个转折加四次变成5，那还差一个结尾端点没算。所以正确答案是把res初始化为1，循环中每个转折加1，结束时需要加1？不对，如果每个转折都加1，首尾两个端点怎么算？
朴素的统计方式：波峰波谷加上首尾端点。序列[1,7,4,9,2,5]首尾是1和5，中间波峰波谷交替出现，所以总数是4+2=6。代码里res初始为1算第一个端点，然后每次转折加1算波峰波谷，这样得到1+4=5，还差最后一个端点。
这个矛盾说明什么？说明题目允许删除元素时，序列的结尾元素不构成波峰或波谷也可以加入。处理办法是在初始化res时，用nums.size()>1 ? 1 : nums.size()作为初始值，然后仍然每次转折加1，最后再补上结尾？具体怎么改？
正确的贪心实现需要注意：首尾两个元素天然属于最长摆动序列。res初始化为1只代表首元素，当第一次出现满足条件的转折时加1，之后每次转折加1，循环结束还需要判断最后一个元素是否能够计入？实际上题目中最后元素之所以能被计入，是因为它在最后一次转折后一定是合法的端点。所以更稳妥的做法是：res初始值为1，循环中每遇到一次转折就res++，循环结束后不需要额外的加一，因为遇到最后一个有效转折时已经包含了结尾端点。让我重新数：
[1,7,4,9,2,5]，首元素1是起点不算转折。循环里发现的转折：i=1是波峰7、i=2是波谷4、i=3是波峰9、i=4是波谷2，共4个转折。res初始为1代表首元素或第一个转折前的平凡元素，每次转折加1，则res=5。那还差结尾元素5呢？如果结尾元素也算，就是6。
问题出在：摆动序列可以只由一个端点构成，也可以由端点加转折构成。这里所有转折都计入了，但结尾5不是转折，怎么算？
查阅标准答案，标准答案是：
- res初始化为1
- 循环i从0到n-2
- 如果满足条件就res++，同时更新prediff 这样[1,7,4,9,2,5]输出的res是6。让我重新跑一下标准写法，我怀疑我上面的模拟错了：
标准写法里prediff初始为0，res初始为1。
i=0: curdiff=6，if (prediff>=0 && curdiff<0) || (prediff<=0 && curdiff>0)，即(0>=0 && 6<0)false || (0<=0 && 6>0)true，所以满足。res++ -> 2，prediff=6。 i=1: curdiff=-3，(6>=0 && -3<0)true，res++ -> 3，prediff=-3。 i=2: curdiff=5，(-3<=0 && 5>0)true，res++ -> 4，prediff=5。 i=3: curdiff=-7，(5>=0 && -7<0)true，res++ -> 5，prediff=-7。 i=4: curdiff=3，(-7<=0 && 3>0)true，res++ -> 6，prediff=3。
输出6。原来如此，我第一次手动模拟时少算了一次，第一个差分6也算作一次转折（因为首元素1可以视为一个端点，紧接着上升的6被计入）。所以答案是6，没有问题。
这个例子说明一件事：初始res=1代表数组的首元素，而每一次转折的计数，实际上是把"转折点后的下一个元素"作为新的端点纳入序列，所以最终结果是首元素加上所有转折点的数量。如果数组全相同，比如[1,1,1]，则没有任何转折，res保持1，正确。
3.5 另一种思路：动态规划解法对照
贪心写法已经足够简洁，但376也有标准的动态规划做法。定义dp[i][0]为前i个元素中以下降结尾的最长摆动序列长度，dp[i][1]为以上升结尾的最长摆动序列长度，转移方程为：
- 如果nums[i] > nums[i-1]，则dp[i][1] = dp[i-1][0] + 1，dp[i][0] = dp[i-1][0]。
- 如果nums[i] < nums[i-1]，则dp[i][0] = dp[i-1][1] + 1，dp[i][1] = dp[i-1][1]。
- 如果相等，则dp[i][0] = dp[i-1][0]，dp[i][1] = dp[i-1][1]。
我在本地两个版本都跑过，答案完全一致。动态规划的优势是转移思路直白，适合讲解；贪心的优势是代码短，常数小。面试时如果你能先讲贪心思路，再补一句"也可以用动态规划做，状态定义是balabala"，会显得你对问题的理解非常透彻。
4. 53. 最大子序和：贪心遇到"负数收益"该怎么止损
4.1 题解：连续子数组最大和
53题给了你一个数组，要求找出一个连续子数组，使得子数组的和最大，返回这个最大值。经典示例是[-2,1,-3,4,-1,2,1,-5,4]，最大子数组是[4,-1,2,1]，和是6。
这道题最直接的解法是三重枚举或者前缀和枚举，O(n^2)能过一部分数据但不够优雅。作为贪心专题的收尾题，它考察的不是如何枚举，而是如何利用"和一旦变负就立刻放弃"这一直觉。
4.2 为什么count变成负数就重置
如果当前累积到的连续和sum是负数，它对后续元素的最大和有没有帮助？答案是没有任何帮助，反而会拖累后面的正数。举个例子，如果你想从a走到b，无论a是正还是负，最划算的方式都是"从b开始走"，而不是背着a这个负数负重前行。
用一个变量count累加当前连续段的和，另一个变量result记录全局最大值。每遍历到一个元素，先count += nums[i]，然后result = max(result, count)。关键来了：如果count小于0，就把count重置为0，表示这一段已经不具备续接价值，从下一个元素重新开始。
反过来也能理解：如果count为正，它就是继续累加的"动力源"，可能让后面的子数组更大。所以核心就一句话：永远不要把一个负数累加段带进未来。
4.3 纯负数数组的边界处理
这个reset策略在纯负数数组上要格外小心。比如[-1,-2,-3]，逐元素跑：
- i=0: count=-1，result更新为max(初始result, -1)，result被设成-1，然后count<0重置为0。
- i=1: count=-2，result更新为max(-1, -2)=-1，count重置为0。
- i=2: count=-3，result更新为max(-1, -3)=-1，重置。
最终返回-1，正确。关键就在于先更新result再重置count，顺序反了就会把所有负数都丢掉，最后返回0，直接WA。这个顺序问题是我第一次做题时踩的坑，网上很多讲解都只强调重置逻辑，没有强调跟result的先后关系，但对纯负数场景来说，这一步就是生死线。
4.4 代码实现与动态规划对照
贪心参考代码如下：
class Solution { public: int maxSubArray(vector<int>& nums) { int result = INT_MIN; int count = 0; for (int i = 0; i < nums.size(); i++) { count += nums[i]; if (count > result) result = count; if (count < 0) count = 0; } return result; } };对应的动态规划写法是经典的Kadane思想，dp[i]表示以i结尾的最大子数组和，状态方程是dp[i] = max(dp[i-1] + nums[i], nums[i])，注意dp[i-1]为负时取nums[i]，
再用滚动变量压缩就是上面这个贪心写法。所以这道题其实是贪心和动态规划两条思路的交汇点，你从两条路径想，最后都会落脚到同一个代码形态。这种题最适合用来检验自己对两类算法的理解程度：如果你能同时解释清楚"为什么贪心对"和"为什么dp[i]的转移长这个样"，说明你是真懂了。
5. 一天三道题的横向复盘：贪心模型、证明直觉与打卡节奏
5.1 三道题的贪心模型对比
做完之后我做了一张对比表，方便以后复习时一眼看穿每道题的结构：
| 题目 | 贪心策略 | 预处理 | 核心复杂度 | 我最容易错的地方 |
|---|---|---|---|---|
| 455.分发饼干 | 小饼干优先喂小胃口孩子 | 两个数组排序 | 排序主导 | 双指针内层循环写错、空数组处理 |
| 376.摆动序列 | 只统计波峰波谷转折点 | 无需预排序 | O(n) | prediff更新时机、平坡边界 |
| 53.最大子序和 | 累加和为负就重置 | 无需预排序 | O(n) | 负数数组下result与count的更新顺序 |
这张表我建议你自己也画一份，画完就能发现，排序是否必要取决于你要不要事先建立一个"可比较的顺序"。455需要排序是因为分配问题天然依赖大小顺序，376和53不需要，因为它们只关心相邻元素的相对变化。
5.2 关于贪心算法的证明，我的实操心得
有个问题我特别想单独拿出来说，就是贪心算法的证明。很多人说刷贪心题不需要证明，背题就行。我的体会是：做题可以靠背，但面试、比赛、甚至工作后的代码评审里，你说不出"为什么这个贪心是对的"，别人很难相信你的方案。
我自己比较常用的验证手段有三种，按成本从低到高排列：
第一种是举反例。设计几种极端情况，如果贪心策略在极端情况翻车，说明策略有问题。455题你试试g=[10,20], s=[5,15,21]，按小饼干喂小胃口不会翻车；376题你试试[1,1,1,1,1]，确认最终返回1；53题你试试全负数数组，确认不会返回0。
第二种是替换论证，就是我前面在455里讲的方法。假设一个最优解存在，证明贪心选择的那个元素可以被塞进某个最优解，且不破坏性质。这个方法在面试中讲出来效果最好。
第三种是相邻交换法，多用于排序型贪心。如果两个相邻决策的顺序互换了不会让结果变差，说明当前排序标准可以贪心选择。这个方法推导成本高一点，但能覆盖很多调度类问题。
三道题里，455最适合练习替换论证，53最适合用贪心选择的"无后效性"来解释，376则适合用动态规划作为验证手段。把每种证明手段都过一遍，你的贪心题感会提升一大截。
5.3 算法训练营打卡的真实收益与建议
最后聊点训练营节奏本身。打卡第27天，说实话前面二十多天里，我有几天是勉强跟上的，尤其是二叉树那一周，很多内容需要反复看两遍才能消化。但进入贪心这一周反而顺畅了一些，因为贪心的代码短，每题的核心逻辑拆开只有几行，只要思路通了，写出来特别有成就感。这也说明一个现象：刷题前期比的不是谁更聪明，而是谁能在"看不懂"的阶段继续往下走。代码随想录把题目按专题排好，重要的不是你今天写没写出来，而是明天回看时你能不能独立把思路复述一遍。
我每天打卡时固定做一个动作：在代码里用注释写一行"我为什么这样贪心"。比如455的那行注释是"最小的饼干喂最小胃口，保留大饼干应对大胃口"，376的那行注释是"只在转折时更新prediff，防止平坡干扰"，53的那行注释是"先更新result再重置count，确保负数数组正确"。这行注释成了我三天后复习时的路标，比记一堆笔记都管用。如果你也在打卡，强烈建议试一试这个办法。
三道题做下来，最大的收获不是背会了三个题解，而是开始建立一种条件反射：拿到新问题，先问能不能排序，再问每一步的局部最优操作是什么，最后用极端用例验证一下。这套思维方式才是第27天真正留给我的东西。
