代码随想录算法训练营打卡进行到第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(vectorint g, vectorint 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(vectorint 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]为例走一遍i0curdiff6prediff0不满足波峰波谷res保持1。i1curdiff-3prediff0prediff0且curdiff0波峰出现res变2prediff更新为-3。i2curdiff5prediff-3prediff0且curdiff0波谷出现res变3prediff更新为5。i3curdiff-7prediff5波峰出现res变4。i4curdiff3prediff-7波谷出现res变5。等等我说到这里发现结果应该是6而不是5大家仔细看代码就会发现循环只到nums.size()-2也就是说最后一个差值curdiff在i4时已经计算了nums[5]-nums[4]2-5-3附近我再完整跑一下i4计算的是nums[5]-nums[4]5-2不对我得重写一下我实际跑的数据。实际数组[1,7,4,9,2,5]长度6。循环i从0到4i0: nums[1]-nums[0]6prediff0不满足res1i1: nums[2]-nums[1]-3满足prediff0 curdiff0res2prediff-3i2: nums[3]-nums[2]5满足prediff0 curdiff0res3prediff5i3: nums[4]-nums[3]-7满足prediff0 curdiff0res4prediff-7i4: nums[5]-nums[4]3满足prediff0 curdiff0res5prediff3得到res5。但示例里[1,7,4,9,2,5]应该输出6。是我写错了吗其实没有因为题目允许删除元素这里每个元素都已经形成转折结尾元素天然可以加入序列所以res为5是错的正确答案是6。原因出在哪问题出在res初始化为1但漏掉了结尾元素。让我们重新推导循环判断的是转折点每出现一个波峰或波谷res就加1。初始res1代表第一个元素本身。最后一个元素天然可以作为序列的末尾不需要再通过转折条件判断。因此上面的5次转折判断只能加5次不对数组[1,7,4,9,2,5]应该有三个波峰两个波谷转折次数是4加上首尾就是6。而我上面的模拟里只加了4次res5说明模拟错了。我再仔细跑一遍其实在i1、i2、i3、i4处各加一次共加4次res145。还是5。但答案应该是6。哪里漏了我重新对照转折点应该是下标17、24、39、42共四个转折加上首尾两个端点总长度是6。res初始为1代表第一个端点四个转折加四次变成5那还差一个结尾端点没算。所以正确答案是把res初始化为1循环中每个转折加1结束时需要加1不对如果每个转折都加1首尾两个端点怎么算朴素的统计方式波峰波谷加上首尾端点。序列[1,7,4,9,2,5]首尾是1和5中间波峰波谷交替出现所以总数是426。代码里res初始为1算第一个端点然后每次转折加1算波峰波谷这样得到145还差最后一个端点。这个矛盾说明什么说明题目允许删除元素时序列的结尾元素不构成波峰或波谷也可以加入。处理办法是在初始化res时用nums.size()1 ? 1 : nums.size()作为初始值然后仍然每次转折加1最后再补上结尾具体怎么改正确的贪心实现需要注意首尾两个元素天然属于最长摆动序列。res初始化为1只代表首元素当第一次出现满足条件的转折时加1之后每次转折加1循环结束还需要判断最后一个元素是否能够计入实际上题目中最后元素之所以能被计入是因为它在最后一次转折后一定是合法的端点。所以更稳妥的做法是res初始值为1循环中每遇到一次转折就res循环结束后不需要额外的加一因为遇到最后一个有效转折时已经包含了结尾端点。让我重新数[1,7,4,9,2,5]首元素1是起点不算转折。循环里发现的转折i1是波峰7、i2是波谷4、i3是波峰9、i4是波谷2共4个转折。res初始为1代表首元素或第一个转折前的平凡元素每次转折加1则res5。那还差结尾元素5呢如果结尾元素也算就是6。问题出在摆动序列可以只由一个端点构成也可以由端点加转折构成。这里所有转折都计入了但结尾5不是转折怎么算查阅标准答案标准答案是res初始化为1循环i从0到n-2如果满足条件就res同时更新prediff 这样[1,7,4,9,2,5]输出的res是6。让我重新跑一下标准写法我怀疑我上面的模拟错了标准写法里prediff初始为0res初始为1。i0: curdiff6if (prediff0 curdiff0) || (prediff0 curdiff0)即(00 60)false || (00 60)true所以满足。res - 2prediff6。 i1: curdiff-3(60 -30)trueres - 3prediff-3。 i2: curdiff5(-30 50)trueres - 4prediff5。 i3: curdiff-7(50 -70)trueres - 5prediff-7。 i4: curdiff3(-70 30)trueres - 6prediff3。输出6。原来如此我第一次手动模拟时少算了一次第一个差分6也算作一次转折因为首元素1可以视为一个端点紧接着上升的6被计入。所以答案是6没有问题。这个例子说明一件事初始res1代表数组的首元素而每一次转折的计数实际上是把转折点后的下一个元素作为新的端点纳入序列所以最终结果是首元素加上所有转折点的数量。如果数组全相同比如[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] 1dp[i][0] dp[i-1][0]。如果nums[i] nums[i-1]则dp[i][0] dp[i-1][1] 1dp[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]逐元素跑i0: count-1result更新为max(初始result, -1)result被设成-1然后count0重置为0。i1: count-2result更新为max(-1, -2)-1count重置为0。i2: count-3result更新为max(-1, -3)-1重置。最终返回-1正确。关键就在于先更新result再重置count顺序反了就会把所有负数都丢掉最后返回0直接WA。这个顺序问题是我第一次做题时踩的坑网上很多讲解都只强调重置逻辑没有强调跟result的先后关系但对纯负数场景来说这一步就是生死线。4.4 代码实现与动态规划对照贪心参考代码如下class Solution { public: int maxSubArray(vectorint 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]确认最终返回153题你试试全负数数组确认不会返回0。第二种是替换论证就是我前面在455里讲的方法。假设一个最优解存在证明贪心选择的那个元素可以被塞进某个最优解且不破坏性质。这个方法在面试中讲出来效果最好。第三种是相邻交换法多用于排序型贪心。如果两个相邻决策的顺序互换了不会让结果变差说明当前排序标准可以贪心选择。这个方法推导成本高一点但能覆盖很多调度类问题。三道题里455最适合练习替换论证53最适合用贪心选择的无后效性来解释376则适合用动态规划作为验证手段。把每种证明手段都过一遍你的贪心题感会提升一大截。5.3 算法训练营打卡的真实收益与建议最后聊点训练营节奏本身。打卡第27天说实话前面二十多天里我有几天是勉强跟上的尤其是二叉树那一周很多内容需要反复看两遍才能消化。但进入贪心这一周反而顺畅了一些因为贪心的代码短每题的核心逻辑拆开只有几行只要思路通了写出来特别有成就感。这也说明一个现象刷题前期比的不是谁更聪明而是谁能在看不懂的阶段继续往下走。代码随想录把题目按专题排好重要的不是你今天写没写出来而是明天回看时你能不能独立把思路复述一遍。我每天打卡时固定做一个动作在代码里用注释写一行我为什么这样贪心。比如455的那行注释是最小的饼干喂最小胃口保留大饼干应对大胃口376的那行注释是只在转折时更新prediff防止平坡干扰53的那行注释是先更新result再重置count确保负数数组正确。这行注释成了我三天后复习时的路标比记一堆笔记都管用。如果你也在打卡强烈建议试一试这个办法。三道题做下来最大的收获不是背会了三个题解而是开始建立一种条件反射拿到新问题先问能不能排序再问每一步的局部最优操作是什么最后用极端用例验证一下。这套思维方式才是第27天真正留给我的东西。
