Day28了说实话走到这个阶段每天打开 LeetCode 已经不是靠意志力硬撑而是刷题这件事本身变成了生活习惯。今天的四道题是典型的贪心算法专场122 买卖股票的最佳时机 II、55 跳跃游戏、45 跳跃游戏 II、1005 K 次取反后最大化的数组和。这四道题难度跨度从简单到中等都是面试里出现频率很高的经典题尤其适合用来检验一件事——你到底是背会了模板还是真的理解了贪心的适用条件。贪心算法最迷惑人的地方在于很多题的解法看起来就是一行max、一个循环几分钟就写完了但为什么这样写是对的很多人说不清楚。今天这篇就拿这四道题当标本把贪心的局部最优推导全局最优这条主线从头到尾捋一遍顺带把我刷题过程中踩过的坑、一开始没想通的点、以及后来怎么绕出来的过程都写出来给同样卡在贪心这块的朋友做个参考。1. 四道贪心题为什么值得放在同一天练先看懂题目在考什么很多人刷题有个习惯按题号刷刷到哪算哪。我建议反过来按算法主题刷一天内把同一类题串起来练效率会高很多。今天这四道题就是我自己排的一组贪心专项它们表面上是股票、跳跃、取反三个完全不相干的场景内核却是同一条线每一步都做当前看起来最优的选择并证明这个局部最优能累加成全局最优。1.1 贪心算法到底在贪什么先给没接触过贪心的朋友一个直觉理解。贪心算法和动态规划经常被放在一起比较两者的核心差别在于动态规划会保存所有子问题的答案最后挑一个最优的贪心则不管那么多它在每个决策点只选眼下收益最大的那条路然后一路走下去不再回头。举个例子你去自助餐厅吃饭限定时间内的目标是吃回本。动态规划的思路是把所有菜品组合都算一遍看哪种搭配总价最高贪心的思路是每次只拿当前单价最贵的那盘吃完再去拿第二贵的。贪心不一定在所有场景下都能得到最优解但在满足贪心选择性质和最优子结构的题目里它就是最省事、效率最高的解法。今天这四道题恰好分别对应了贪心的几种常见套路区间拆分累加122、覆盖范围维护55、覆盖范围加计数45、排序后按条件处理1005。把它们放在一起你就能看出贪心题的大致面貌下次遇到类似的题至少知道往哪个方向去试。1.2 四道题的共性主线与递进关系这四道题的递进关系非常明显我甚至觉得 LeetCode 的题目顺序是故意这么排的122 题是最简单的贪心入门只需要把相邻两天上涨的差价全部累加不需要考虑任何复杂的持有状态。55 题开始需要一点抽象能力不是让你真的去模拟怎么跳而是维护一个最远能覆盖到哪里的范围。45 题是 55 题的加强版不仅判断能不能到终点还要计算最少跳几次贪心策略从维护覆盖范围升级为在边界处结算步数。1005 题则换了个角度贪心对象不是路径而是排序顺序处理完负数之后还要考虑剩余次数的奇偶性。我建议按这个顺序刷因为每道题都会用到上一道题的思维工具。单独做任何一道都可能觉得哦就这么写呗四道连起来做才能感受到贪心的思考方式是怎么一步一步升级的。2. 122 题把低买高卖拆成相邻差值是这题最关键的思维转换先看题。给定一个数组pricesprices[i]表示第i天的股票价格。你可以在任意一天买入、任意一天卖出但同一时间只能持有一笔交易也就是说卖完才能再买。要求返回能获得的最大利润。注意这题和第 121 题长得像但完全不同121 题只允许买卖一次这道题不限交易次数。2.1 贪心策略的推导过程为什么累加正差价就够了我第一次做这题的时候思路还是 121 题的惯性找波谷买入、波峰卖出然后继续找下一段波谷波峰。这个思路也能做但实现起来要维护一堆状态很容易在边界条件上出错。后来看了官方题解才反应过来这题有一个更优雅的等价变换对于任意一段从第 i 天到第 j 天的上涨行情prices[j] - prices[i]可以拆成若干相邻差值的和(prices[i1] - prices[i]) (prices[i2] - prices[i1]) ... (prices[j] - prices[j-1])。这意味着我不需要去管哪天买入、哪天卖出只需要遍历数组把所有正数的相邻差值累加起来。每次遇到prices[i] - prices[i-1] 0就说明这天的价格比前一天高这段上涨我是能赚到的赚到就完事。跌的那天我不买自然不会有亏损。为什么这是贪心因为在每个相邻两天的决策点上我都选择只要涨就赚这个局部最优因为交易次数不限这些局部最优累加起来正好等于全局最优。你可以把股票交易想象成每天都看一次行情涨了就拿前一天买入的份额赚一笔跌了就不动这正是贪心走一步看一步的体现。2.2 这个策略的正确性证明与边界情况严谨一点的证明也不难设所有相邻正差价之和为sum任意一种交易策略的利润都等于若干段卖出价减去买入价也就是若干段相邻差值的和。因为每段相邻差值最多被计入一次、且不会超过它的正值本身所以任意策略的利润都不会超过sum。反过来我按每天涨了就赚的方式操作刚好能拿到sum所以sum就是最大利润。边界情况也挺有意思数组长度只有 1那利润就是 0因为根本没有第二天可以卖。价格一直下跌比如[5, 4, 3, 2, 1]所有相邻差值都是负数累加结果就是 0规则上不买不卖就是最优。价格反复震荡比如[1, 2, 1, 2, 1, 2]我的策略会把每次1 涨到 2的 1 块钱都赚到总利润 3。如果你手动找波谷波峰得到的结果也是一样的但代码复杂度完全不是一个量级。def maxProfit(prices: list[int]) - int: profit 0 for i in range(1, len(prices)): diff prices[i] - prices[i - 1] if diff 0: profit diff return profit2.3 和 121 题放进一起对比为什么这里的每天都卖是合法的新手最容易在这个地方卡壳如果我每天都卖出再买入会不会违反同时只能持有一笔交易的约束实际上不会因为我把交易拆成了当天卖出、当天再买入的连续操作这在规则上完全等价于一直持有到更高点再卖。比如三天价格[1, 2, 3]拆开做是第 1 天买第 2 天卖赚 1第 2 天再买第 3 天卖赚 1总共赚 2等价于第 1 天买第 3 天卖赚 2。这也是贪心题的一个典型特征同一个结果可以用不同方式达成贪心选择的是拆得最细、最容易写的那一种方式。如果你在做这道题时还在纠结买卖时机怎么选择不妨停下来想一遍这个等价关系思路会通很多。3. 55 题和 45 题跳跃游戏的核心是维护覆盖范围不是模拟跳跃这两道题在网上的搜索量一直很高很多人搜跳跃游戏 贪心算法找到题解后第一反应是代码这么短但我完全想不通它为什么能保证答案正确。这很正常因为跳跃游戏考察的不是怎么跳而是能覆盖到哪里。3.1 55 题最远可达范围的递推55 题的要求很简单给定一个非负整数数组nums你从下标 0 出发nums[i]表示你在位置 i 最多能向前跳多远。判断能否到达最后一个下标。很多人一开始会想用回溯从每个位置枚举跳几步直到走到终点或者走不动。这个思路在小数组上没问题但一旦数组变长递归分支数会爆炸直接超时。正确的贪心思路是我不关心具体选哪条路只关心从当前已经能到达的所有位置出发最远能推到多远。具体做法是维护一个变量max_reach初始化为nums[0]。遍历数组对于每个位置i如果i max_reach说明前面已经出现了一个断点无论怎么跳都到不了位置 i直接返回 False。否则说明位置 i 是可以到达的用i nums[i]更新max_reach max(max_reach, i nums[i])。如果过程中max_reach len(nums) - 1直接返回 True。def canJump(nums: list[int]) - bool: max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return False为什么这个贪心是安全的因为max_reach的含义是当前可达区域的最右边界在这个边界之内的所有位置理论上都可以通过某条路径到达。我只需要不断扩大这个边界直到它覆盖末尾。跳跃的具体步法不重要重要的是能覆盖到和不能覆盖到的边界在哪里。这就好比你要判断一片区域能不能被几个信号塔覆盖你不需要规划每个手机怎么连只需要看信号塔的总覆盖半径是否连成一片。补充一个面试官可能会追问的变体思路从后往前遍历也能做。维护一个变量need表示从当前位置出发至少需要能跳多远才能到达末尾。初始need 1从倒数第二个位置往前扫如果nums[i] need说明从 i 可以直接跳到末尾那么前面的位置只需要能到 i 就行于是把need重置为 1否则need 1。最后检查need 1。这个写法在思路上更绕但可以作为理解覆盖范围的辅助练习。3.2 45 题在覆盖范围边界才结算步数45 题是 55 题的加强版输入保证能到达末尾要求返回最少跳跃次数。这题的核心难点不是能不能到而是怎么让次数最少。贪心思路可以这样理解把跳跃过程划分成每一跳能覆盖的区间。第一次跳跃从下标 0 出发能覆盖到下标0 nums[0]在这个区间内的任何一个位置都可以作为第二次跳跃的起跳点所以第二次跳跃能覆盖到的最远距离是区间内所有i nums[i]的最大值。依此类推每次当遍历到当前覆盖区间的边界时才真正跳一次并把边界更新为前面算出的最大值。实现时维护三个变量cur_end当前这一跳能覆盖到的最远下标。next_max在当前覆盖区间内遍历时算出的下一跳能覆盖到的最远下标。steps跳跃次数。遍历i从 0 到n - 2最后一个位置不用起跳不断更新next_max。当i cur_end时说明当前这一跳已经用尽了必须再跳一次于是steps 1cur_end next_max。如果某次更新后cur_end n - 1直接跳出循环。def jump(nums: list[int]) - int: n len(nums) if n 1: return 0 cur_end 0 next_max 0 steps 0 for i in range(n - 1): next_max max(next_max, i nums[i]) if i cur_end: steps 1 cur_end next_max if cur_end n - 1: break return steps关键点在于只在边界结算步数。很多第一次接触这道题的人会写成每次都跳到i nums[i]最远的地方然后步数加一再继续从那里跳。这个思路在部分用例上是错的因为你当前位置能跳到的最远点不一定是下一跳的最佳起点最佳策略是停留在当前覆盖区间内的某个位置让下一跳覆盖得更远。所以不是每次都跳最远而是每次在当前可达范围内选一个能让下一步覆盖更远的起跳点这就是贪心里的延迟决策。3.3 两道跳跃题的边界条件实测跳跃题看着简单边界条件一测就容易翻车nums [0]已经在下标 0也就是最后一个位置55 题应该返回 True45 题应该返回 0。很多人会忽略这个特判。nums [0, 1]55 题应该返回 False因为下标 0 的跳力是 0根本到不了下标 1。45 题输入保证可到达所以不会出现这种用例。nums [1, 2, 3]45 题最少是 2 步从 0 跳到 1再从 1 跳到 2。模拟一下流程i0时next_max变成 1此时i cur_end 0跳一次cur_end 1i1时next_max变成 3此时i cur_end 1再跳一次cur_end 3已经到末尾。步数 2正确。全 1 数组[1, 1, 1, 1]每次只能跳一格步数就是 3。贪心过程是每走一步就结算一次结果也是 3。这两题的代码量都很小我建议刷完之后手动把几个典型用例的变量变化过程写在纸上比看十遍题解都有用。我一开始就是懒得手推觉得代码能过就行结果过了几天回头复习发现自己已经忘了为什么要这么写又花时间重看了一遍题解。对于贪心题手推过程比记住代码重要得多。4. 1005 题绝对值排序才是本题题眼剩余 K 的奇偶性决定最终答案1005 题的场景是给你一个整数数组nums和一个整数k每次操作可以选择数组中任意一个下标 i将nums[i]取反正变负、负变正恰好执行 k 次返回数组可能的最大和。注意恰好两个字不是最多这是很多人会漏掉的条件。4.1 为什么先按绝对值从大到小排序直觉上要让数组和最大应该尽量把负数变成正数而且绝对值越大的负数变正后的收益越大。举个例子数组[-5, -1, 2]k1显然应该把 -5 变成 5而不是把 -1 变成 1因为前者让总和增加 10后者只增加 2。那么怎么实现优先处理绝对值大的负数最直接的办法是按绝对值从大到小排序。排序之后数组变成[-5, 2, -1]这种顺序按绝对值排遍历时遇到负数就取反同时消耗一次 k。处理完所有负数之后k 可能还有剩余这时候进入第二阶段。这里有个容易犯错的地方如果按普通升序排序比如数组[-5, 1, 2]k1普通排序还是能正确处理第一个负数但如果负数全部取反之后剩下的元素比较大你还需要考虑剩余取反次数应该作用在哪个元素上这时候选错目标就会导致答案偏差。比如[-8, 1, 2, 3]k1普通排序也能过但如果是[-1, -1, 2, 3]k3前两个负数变正消耗 2 次剩 1 次必须把最小的正数 1 取反才能让损失最小。按绝对值排序能让你在这个阶段很自然地找到绝对值最小的元素——也就是排序后数组的最后一个元素。def largestSumAfterKNegations(nums: list[int], k: int) - int: nums.sort(keylambda x: abs(x), reverseTrue) for i in range(len(nums)): if nums[i] 0 and k 0: nums[i] -nums[i] k - 1 if k % 2 1: nums[-1] -nums[-1] return sum(nums)4.2 剩余取反次数的奇偶处理一个数学规律做完第一步之后数组里已经全是非负数了这时还剩下k次操作。你当然可以真的循环 k 次每次把某个数取反但那样会超时而且没必要。这里有一个数学规律对一个数连续取反两次等于没做操作。因为-(-x) x。所以剩余 k 的取值只需看奇偶性如果k是偶数随便你怎么取反最终总和都不变直接忽略剩下的次数。如果k是奇数相当于只能再取反一次那就要选一个让总损失最小的数——也就是绝对值最小的那个元素把它取反。用数学表达就是sum - 2 * min_abs_value。因为把一个数 x 取反后总和从 sum 变成 sum - 2x。这里还有个小细节如果数组里有 0且 k 是奇数对 0 取反不影响结果所以直接当成损失为 0处理代码里nums[-1]可能是 0那就更优了。排序后最后一个元素就是绝对值最小的元素因为按绝对值降序排尾部的元素绝对值一定最小。我之前写过一版先按普通升序排序处理完负数后单独用min(map(abs, nums))去查最小绝对值也能过但逻辑比上面这版绕。按绝对值排序是官方题解的标准思路它把找最大负数和找最小绝对值两个需求一次排序全部解决了。4.3 一个容易忽略的边界k 比负数个数大很多比如数组[-1, 2, 3]k5。第一步把 -1 变成 1消耗 1 次剩 4 次偶数直接忽略答案是 6。但如果 k6剩 5 次奇数需要对绝对值最小的 1原先是 -1 变来的再取反一次损失 2答案是 4。这个过程用先取反再处理奇数的套路走一遍代码完全不需要改动。再比如数组[-3, -2, -1, 4]k4。绝对值排序后是[-3, 4, -2, -1]遍历时把 -3、-2、-1 全部取反消耗 3 次剩余 1 次奇数把最后的最小绝对值元素取反也就是 -1 取反后变成 1再取反回 -1答案自然比其他暴力方案更优。这个例子我当初是手动推了一遍才彻底理解的建议你也挑一个类似用例跟着代码走一遍变量变化。组合起来看1005 这题和前面三道的思考方式有明显区别前三道是顺着遍历维护状态这道是先排序把数据结构理顺再分阶段贪心。这也是贪心的另一种常见形态通过排序让决策顺序有序化之后每一步只要按顺序选择即可。5. 四道题横向复盘复杂度对照表与高频翻车点清单四道题都过了一遍代码和思路最后做一个横向汇总。这一节不只适合刷题也适合面试前快速回顾把关键结论压缩成一张表临场不会慌。5.1 四道题的核心策略与复杂度对照题号场景贪心策略时间复杂度空间复杂度122买卖股票 II累加所有正数相邻差值O(n)O(1)55跳跃游戏维护最远可达范围判断覆盖是否连续O(n)O(1)45跳跃游戏 II在覆盖范围边界结算步数提前算下一步最远距离O(n)O(1)1005K 次取反最大化按绝对值降序排序先翻转负数再处理剩余次数的奇偶性O(n log n)O(1)四道题的共同点是时间复杂度都在 O(n) 或 O(n log n)空间 O(1)这也是贪心算法的魅力所在代码短、速度快。对比动态规划动辄 O(n^2) 的时间、O(n) 或 O(n^2) 的空间贪心在很多场景下都是最优解。但要注意能用贪心不代表所有类似题都能用贪心。比如买卖股票带冷却期309 题、带手续费714 题、跳跃游戏带障碍物变体这些情况下贪心就不一定成立需要转成动态规划或者更复杂的贪心状态机。面试时如果只背了解法不问原理一旦题目变形就会露馅。这也是我为什么在每道题里都要强调为什么这样选是安全的。5.2 刷题过程中我踩过的三个坑第一122 题用 121 题的模板。我第一次做 122 的时候直接套 121 的找一个波谷一个波峰的写法维护了两个变量buy和sell结果在[7, 1, 5, 3, 6, 4]这种用例上能过换成[1, 2, 3, 4, 5]就出错——因为这段全上涨行情里一次交易和多次交易的利润差异非常明显。后来才意识到121 和 122 的区别恰恰是交易次数限制这个约束条件这个条件变了贪心策略就完全不同。第二45 题把每次跳最远当成最优策略。这个误区特别隐蔽因为代码跑出来大部分用例都能过我一度以为这就是正解。直到用[2, 3, 1, 1, 4]手动模拟才发现问题从下标 0 跳 2 步到下标 2然后只能跳 1 步到下标 3再跳 1 步到下标 4总共 3 步但如果从下标 0 先跳 1 步到下标 1再跳 3 步直接到末尾总共只要 2 步。这说明当前跳得最远不等于全局步数最少正确的贪心是在当前覆盖区间内找到能让下一步覆盖最远的位置也就是延迟决策直到边界才结算。第三1005 题忘记处理剩余 k 的奇偶性。我第一版代码只做了负数取反这一步提交后在[-1, 2, 3], k 3这个用例上直接 WA。当时觉得k3负数只有一个取反一次之后 k 还剩 2不知道该怎么办。后来才意识到剩余次数不能不处理必须根据奇偶性决定是否翻转最小绝对值元素。这也是题目里恰好 k 次的用意逼着你考虑用不完的次数怎么消化。5.3 一个可复用的贪心题动手前检查单经过这四道题的训练我总结出一个做贪心题的动手前检查单每次拿到新题都按这个顺序过一遍能少走很多弯路明确约束条件交易次数是否受限必须恰好执行 K 次还是最多 K 次数组元素是否可能为 0这些细节直接决定贪心策略形态。尝试描述局部最优用一句话说清楚我每一步在选择什么。比如 122 是涨就赚55 是扩大可达边界45 是边界才结算1005 是优先翻转绝对值大的负数。判断局部最优能否推出全局最优可以通过数学归纳、交换论证或者至少手动模拟几个极端用例。想不通就换动态规划试试别硬套贪心。考虑是否需要排序如果决策对象有优先级之分比如绝对值大小、剩余步数多少排序常常是贪心的前置步骤。手推一个典型用例再写代码先用小数组把变量变化过程推一遍再写代码正确率会高很多也方便之后复习。跳出来看今天这四道题本质上是贪心的四种手感加法型贪心、覆盖型贪心、覆盖加计数型贪心、排序型贪心。贪心算法的知识点本身很浅浅到一句话就能说完但真正拉开差距的是你能不能判断这道题能不能贪。我自己的体会是判断能力没有捷径只能靠题量喂出来而且每一道题都要强迫自己说出为什么这个局部最优是安全的而不是写完 AC 就翻篇。坚持这样做一段时间再看到新题时你对该不该用贪心的第一感觉会准很多。
贪心算法四题详解：从买卖股票到跳跃游戏，掌握局部最优推导全局最优
Day28了说实话走到这个阶段每天打开 LeetCode 已经不是靠意志力硬撑而是刷题这件事本身变成了生活习惯。今天的四道题是典型的贪心算法专场122 买卖股票的最佳时机 II、55 跳跃游戏、45 跳跃游戏 II、1005 K 次取反后最大化的数组和。这四道题难度跨度从简单到中等都是面试里出现频率很高的经典题尤其适合用来检验一件事——你到底是背会了模板还是真的理解了贪心的适用条件。贪心算法最迷惑人的地方在于很多题的解法看起来就是一行max、一个循环几分钟就写完了但为什么这样写是对的很多人说不清楚。今天这篇就拿这四道题当标本把贪心的局部最优推导全局最优这条主线从头到尾捋一遍顺带把我刷题过程中踩过的坑、一开始没想通的点、以及后来怎么绕出来的过程都写出来给同样卡在贪心这块的朋友做个参考。1. 四道贪心题为什么值得放在同一天练先看懂题目在考什么很多人刷题有个习惯按题号刷刷到哪算哪。我建议反过来按算法主题刷一天内把同一类题串起来练效率会高很多。今天这四道题就是我自己排的一组贪心专项它们表面上是股票、跳跃、取反三个完全不相干的场景内核却是同一条线每一步都做当前看起来最优的选择并证明这个局部最优能累加成全局最优。1.1 贪心算法到底在贪什么先给没接触过贪心的朋友一个直觉理解。贪心算法和动态规划经常被放在一起比较两者的核心差别在于动态规划会保存所有子问题的答案最后挑一个最优的贪心则不管那么多它在每个决策点只选眼下收益最大的那条路然后一路走下去不再回头。举个例子你去自助餐厅吃饭限定时间内的目标是吃回本。动态规划的思路是把所有菜品组合都算一遍看哪种搭配总价最高贪心的思路是每次只拿当前单价最贵的那盘吃完再去拿第二贵的。贪心不一定在所有场景下都能得到最优解但在满足贪心选择性质和最优子结构的题目里它就是最省事、效率最高的解法。今天这四道题恰好分别对应了贪心的几种常见套路区间拆分累加122、覆盖范围维护55、覆盖范围加计数45、排序后按条件处理1005。把它们放在一起你就能看出贪心题的大致面貌下次遇到类似的题至少知道往哪个方向去试。1.2 四道题的共性主线与递进关系这四道题的递进关系非常明显我甚至觉得 LeetCode 的题目顺序是故意这么排的122 题是最简单的贪心入门只需要把相邻两天上涨的差价全部累加不需要考虑任何复杂的持有状态。55 题开始需要一点抽象能力不是让你真的去模拟怎么跳而是维护一个最远能覆盖到哪里的范围。45 题是 55 题的加强版不仅判断能不能到终点还要计算最少跳几次贪心策略从维护覆盖范围升级为在边界处结算步数。1005 题则换了个角度贪心对象不是路径而是排序顺序处理完负数之后还要考虑剩余次数的奇偶性。我建议按这个顺序刷因为每道题都会用到上一道题的思维工具。单独做任何一道都可能觉得哦就这么写呗四道连起来做才能感受到贪心的思考方式是怎么一步一步升级的。2. 122 题把低买高卖拆成相邻差值是这题最关键的思维转换先看题。给定一个数组pricesprices[i]表示第i天的股票价格。你可以在任意一天买入、任意一天卖出但同一时间只能持有一笔交易也就是说卖完才能再买。要求返回能获得的最大利润。注意这题和第 121 题长得像但完全不同121 题只允许买卖一次这道题不限交易次数。2.1 贪心策略的推导过程为什么累加正差价就够了我第一次做这题的时候思路还是 121 题的惯性找波谷买入、波峰卖出然后继续找下一段波谷波峰。这个思路也能做但实现起来要维护一堆状态很容易在边界条件上出错。后来看了官方题解才反应过来这题有一个更优雅的等价变换对于任意一段从第 i 天到第 j 天的上涨行情prices[j] - prices[i]可以拆成若干相邻差值的和(prices[i1] - prices[i]) (prices[i2] - prices[i1]) ... (prices[j] - prices[j-1])。这意味着我不需要去管哪天买入、哪天卖出只需要遍历数组把所有正数的相邻差值累加起来。每次遇到prices[i] - prices[i-1] 0就说明这天的价格比前一天高这段上涨我是能赚到的赚到就完事。跌的那天我不买自然不会有亏损。为什么这是贪心因为在每个相邻两天的决策点上我都选择只要涨就赚这个局部最优因为交易次数不限这些局部最优累加起来正好等于全局最优。你可以把股票交易想象成每天都看一次行情涨了就拿前一天买入的份额赚一笔跌了就不动这正是贪心走一步看一步的体现。2.2 这个策略的正确性证明与边界情况严谨一点的证明也不难设所有相邻正差价之和为sum任意一种交易策略的利润都等于若干段卖出价减去买入价也就是若干段相邻差值的和。因为每段相邻差值最多被计入一次、且不会超过它的正值本身所以任意策略的利润都不会超过sum。反过来我按每天涨了就赚的方式操作刚好能拿到sum所以sum就是最大利润。边界情况也挺有意思数组长度只有 1那利润就是 0因为根本没有第二天可以卖。价格一直下跌比如[5, 4, 3, 2, 1]所有相邻差值都是负数累加结果就是 0规则上不买不卖就是最优。价格反复震荡比如[1, 2, 1, 2, 1, 2]我的策略会把每次1 涨到 2的 1 块钱都赚到总利润 3。如果你手动找波谷波峰得到的结果也是一样的但代码复杂度完全不是一个量级。def maxProfit(prices: list[int]) - int: profit 0 for i in range(1, len(prices)): diff prices[i] - prices[i - 1] if diff 0: profit diff return profit2.3 和 121 题放进一起对比为什么这里的每天都卖是合法的新手最容易在这个地方卡壳如果我每天都卖出再买入会不会违反同时只能持有一笔交易的约束实际上不会因为我把交易拆成了当天卖出、当天再买入的连续操作这在规则上完全等价于一直持有到更高点再卖。比如三天价格[1, 2, 3]拆开做是第 1 天买第 2 天卖赚 1第 2 天再买第 3 天卖赚 1总共赚 2等价于第 1 天买第 3 天卖赚 2。这也是贪心题的一个典型特征同一个结果可以用不同方式达成贪心选择的是拆得最细、最容易写的那一种方式。如果你在做这道题时还在纠结买卖时机怎么选择不妨停下来想一遍这个等价关系思路会通很多。3. 55 题和 45 题跳跃游戏的核心是维护覆盖范围不是模拟跳跃这两道题在网上的搜索量一直很高很多人搜跳跃游戏 贪心算法找到题解后第一反应是代码这么短但我完全想不通它为什么能保证答案正确。这很正常因为跳跃游戏考察的不是怎么跳而是能覆盖到哪里。3.1 55 题最远可达范围的递推55 题的要求很简单给定一个非负整数数组nums你从下标 0 出发nums[i]表示你在位置 i 最多能向前跳多远。判断能否到达最后一个下标。很多人一开始会想用回溯从每个位置枚举跳几步直到走到终点或者走不动。这个思路在小数组上没问题但一旦数组变长递归分支数会爆炸直接超时。正确的贪心思路是我不关心具体选哪条路只关心从当前已经能到达的所有位置出发最远能推到多远。具体做法是维护一个变量max_reach初始化为nums[0]。遍历数组对于每个位置i如果i max_reach说明前面已经出现了一个断点无论怎么跳都到不了位置 i直接返回 False。否则说明位置 i 是可以到达的用i nums[i]更新max_reach max(max_reach, i nums[i])。如果过程中max_reach len(nums) - 1直接返回 True。def canJump(nums: list[int]) - bool: max_reach 0 n len(nums) for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return False为什么这个贪心是安全的因为max_reach的含义是当前可达区域的最右边界在这个边界之内的所有位置理论上都可以通过某条路径到达。我只需要不断扩大这个边界直到它覆盖末尾。跳跃的具体步法不重要重要的是能覆盖到和不能覆盖到的边界在哪里。这就好比你要判断一片区域能不能被几个信号塔覆盖你不需要规划每个手机怎么连只需要看信号塔的总覆盖半径是否连成一片。补充一个面试官可能会追问的变体思路从后往前遍历也能做。维护一个变量need表示从当前位置出发至少需要能跳多远才能到达末尾。初始need 1从倒数第二个位置往前扫如果nums[i] need说明从 i 可以直接跳到末尾那么前面的位置只需要能到 i 就行于是把need重置为 1否则need 1。最后检查need 1。这个写法在思路上更绕但可以作为理解覆盖范围的辅助练习。3.2 45 题在覆盖范围边界才结算步数45 题是 55 题的加强版输入保证能到达末尾要求返回最少跳跃次数。这题的核心难点不是能不能到而是怎么让次数最少。贪心思路可以这样理解把跳跃过程划分成每一跳能覆盖的区间。第一次跳跃从下标 0 出发能覆盖到下标0 nums[0]在这个区间内的任何一个位置都可以作为第二次跳跃的起跳点所以第二次跳跃能覆盖到的最远距离是区间内所有i nums[i]的最大值。依此类推每次当遍历到当前覆盖区间的边界时才真正跳一次并把边界更新为前面算出的最大值。实现时维护三个变量cur_end当前这一跳能覆盖到的最远下标。next_max在当前覆盖区间内遍历时算出的下一跳能覆盖到的最远下标。steps跳跃次数。遍历i从 0 到n - 2最后一个位置不用起跳不断更新next_max。当i cur_end时说明当前这一跳已经用尽了必须再跳一次于是steps 1cur_end next_max。如果某次更新后cur_end n - 1直接跳出循环。def jump(nums: list[int]) - int: n len(nums) if n 1: return 0 cur_end 0 next_max 0 steps 0 for i in range(n - 1): next_max max(next_max, i nums[i]) if i cur_end: steps 1 cur_end next_max if cur_end n - 1: break return steps关键点在于只在边界结算步数。很多第一次接触这道题的人会写成每次都跳到i nums[i]最远的地方然后步数加一再继续从那里跳。这个思路在部分用例上是错的因为你当前位置能跳到的最远点不一定是下一跳的最佳起点最佳策略是停留在当前覆盖区间内的某个位置让下一跳覆盖得更远。所以不是每次都跳最远而是每次在当前可达范围内选一个能让下一步覆盖更远的起跳点这就是贪心里的延迟决策。3.3 两道跳跃题的边界条件实测跳跃题看着简单边界条件一测就容易翻车nums [0]已经在下标 0也就是最后一个位置55 题应该返回 True45 题应该返回 0。很多人会忽略这个特判。nums [0, 1]55 题应该返回 False因为下标 0 的跳力是 0根本到不了下标 1。45 题输入保证可到达所以不会出现这种用例。nums [1, 2, 3]45 题最少是 2 步从 0 跳到 1再从 1 跳到 2。模拟一下流程i0时next_max变成 1此时i cur_end 0跳一次cur_end 1i1时next_max变成 3此时i cur_end 1再跳一次cur_end 3已经到末尾。步数 2正确。全 1 数组[1, 1, 1, 1]每次只能跳一格步数就是 3。贪心过程是每走一步就结算一次结果也是 3。这两题的代码量都很小我建议刷完之后手动把几个典型用例的变量变化过程写在纸上比看十遍题解都有用。我一开始就是懒得手推觉得代码能过就行结果过了几天回头复习发现自己已经忘了为什么要这么写又花时间重看了一遍题解。对于贪心题手推过程比记住代码重要得多。4. 1005 题绝对值排序才是本题题眼剩余 K 的奇偶性决定最终答案1005 题的场景是给你一个整数数组nums和一个整数k每次操作可以选择数组中任意一个下标 i将nums[i]取反正变负、负变正恰好执行 k 次返回数组可能的最大和。注意恰好两个字不是最多这是很多人会漏掉的条件。4.1 为什么先按绝对值从大到小排序直觉上要让数组和最大应该尽量把负数变成正数而且绝对值越大的负数变正后的收益越大。举个例子数组[-5, -1, 2]k1显然应该把 -5 变成 5而不是把 -1 变成 1因为前者让总和增加 10后者只增加 2。那么怎么实现优先处理绝对值大的负数最直接的办法是按绝对值从大到小排序。排序之后数组变成[-5, 2, -1]这种顺序按绝对值排遍历时遇到负数就取反同时消耗一次 k。处理完所有负数之后k 可能还有剩余这时候进入第二阶段。这里有个容易犯错的地方如果按普通升序排序比如数组[-5, 1, 2]k1普通排序还是能正确处理第一个负数但如果负数全部取反之后剩下的元素比较大你还需要考虑剩余取反次数应该作用在哪个元素上这时候选错目标就会导致答案偏差。比如[-8, 1, 2, 3]k1普通排序也能过但如果是[-1, -1, 2, 3]k3前两个负数变正消耗 2 次剩 1 次必须把最小的正数 1 取反才能让损失最小。按绝对值排序能让你在这个阶段很自然地找到绝对值最小的元素——也就是排序后数组的最后一个元素。def largestSumAfterKNegations(nums: list[int], k: int) - int: nums.sort(keylambda x: abs(x), reverseTrue) for i in range(len(nums)): if nums[i] 0 and k 0: nums[i] -nums[i] k - 1 if k % 2 1: nums[-1] -nums[-1] return sum(nums)4.2 剩余取反次数的奇偶处理一个数学规律做完第一步之后数组里已经全是非负数了这时还剩下k次操作。你当然可以真的循环 k 次每次把某个数取反但那样会超时而且没必要。这里有一个数学规律对一个数连续取反两次等于没做操作。因为-(-x) x。所以剩余 k 的取值只需看奇偶性如果k是偶数随便你怎么取反最终总和都不变直接忽略剩下的次数。如果k是奇数相当于只能再取反一次那就要选一个让总损失最小的数——也就是绝对值最小的那个元素把它取反。用数学表达就是sum - 2 * min_abs_value。因为把一个数 x 取反后总和从 sum 变成 sum - 2x。这里还有个小细节如果数组里有 0且 k 是奇数对 0 取反不影响结果所以直接当成损失为 0处理代码里nums[-1]可能是 0那就更优了。排序后最后一个元素就是绝对值最小的元素因为按绝对值降序排尾部的元素绝对值一定最小。我之前写过一版先按普通升序排序处理完负数后单独用min(map(abs, nums))去查最小绝对值也能过但逻辑比上面这版绕。按绝对值排序是官方题解的标准思路它把找最大负数和找最小绝对值两个需求一次排序全部解决了。4.3 一个容易忽略的边界k 比负数个数大很多比如数组[-1, 2, 3]k5。第一步把 -1 变成 1消耗 1 次剩 4 次偶数直接忽略答案是 6。但如果 k6剩 5 次奇数需要对绝对值最小的 1原先是 -1 变来的再取反一次损失 2答案是 4。这个过程用先取反再处理奇数的套路走一遍代码完全不需要改动。再比如数组[-3, -2, -1, 4]k4。绝对值排序后是[-3, 4, -2, -1]遍历时把 -3、-2、-1 全部取反消耗 3 次剩余 1 次奇数把最后的最小绝对值元素取反也就是 -1 取反后变成 1再取反回 -1答案自然比其他暴力方案更优。这个例子我当初是手动推了一遍才彻底理解的建议你也挑一个类似用例跟着代码走一遍变量变化。组合起来看1005 这题和前面三道的思考方式有明显区别前三道是顺着遍历维护状态这道是先排序把数据结构理顺再分阶段贪心。这也是贪心的另一种常见形态通过排序让决策顺序有序化之后每一步只要按顺序选择即可。5. 四道题横向复盘复杂度对照表与高频翻车点清单四道题都过了一遍代码和思路最后做一个横向汇总。这一节不只适合刷题也适合面试前快速回顾把关键结论压缩成一张表临场不会慌。5.1 四道题的核心策略与复杂度对照题号场景贪心策略时间复杂度空间复杂度122买卖股票 II累加所有正数相邻差值O(n)O(1)55跳跃游戏维护最远可达范围判断覆盖是否连续O(n)O(1)45跳跃游戏 II在覆盖范围边界结算步数提前算下一步最远距离O(n)O(1)1005K 次取反最大化按绝对值降序排序先翻转负数再处理剩余次数的奇偶性O(n log n)O(1)四道题的共同点是时间复杂度都在 O(n) 或 O(n log n)空间 O(1)这也是贪心算法的魅力所在代码短、速度快。对比动态规划动辄 O(n^2) 的时间、O(n) 或 O(n^2) 的空间贪心在很多场景下都是最优解。但要注意能用贪心不代表所有类似题都能用贪心。比如买卖股票带冷却期309 题、带手续费714 题、跳跃游戏带障碍物变体这些情况下贪心就不一定成立需要转成动态规划或者更复杂的贪心状态机。面试时如果只背了解法不问原理一旦题目变形就会露馅。这也是我为什么在每道题里都要强调为什么这样选是安全的。5.2 刷题过程中我踩过的三个坑第一122 题用 121 题的模板。我第一次做 122 的时候直接套 121 的找一个波谷一个波峰的写法维护了两个变量buy和sell结果在[7, 1, 5, 3, 6, 4]这种用例上能过换成[1, 2, 3, 4, 5]就出错——因为这段全上涨行情里一次交易和多次交易的利润差异非常明显。后来才意识到121 和 122 的区别恰恰是交易次数限制这个约束条件这个条件变了贪心策略就完全不同。第二45 题把每次跳最远当成最优策略。这个误区特别隐蔽因为代码跑出来大部分用例都能过我一度以为这就是正解。直到用[2, 3, 1, 1, 4]手动模拟才发现问题从下标 0 跳 2 步到下标 2然后只能跳 1 步到下标 3再跳 1 步到下标 4总共 3 步但如果从下标 0 先跳 1 步到下标 1再跳 3 步直接到末尾总共只要 2 步。这说明当前跳得最远不等于全局步数最少正确的贪心是在当前覆盖区间内找到能让下一步覆盖最远的位置也就是延迟决策直到边界才结算。第三1005 题忘记处理剩余 k 的奇偶性。我第一版代码只做了负数取反这一步提交后在[-1, 2, 3], k 3这个用例上直接 WA。当时觉得k3负数只有一个取反一次之后 k 还剩 2不知道该怎么办。后来才意识到剩余次数不能不处理必须根据奇偶性决定是否翻转最小绝对值元素。这也是题目里恰好 k 次的用意逼着你考虑用不完的次数怎么消化。5.3 一个可复用的贪心题动手前检查单经过这四道题的训练我总结出一个做贪心题的动手前检查单每次拿到新题都按这个顺序过一遍能少走很多弯路明确约束条件交易次数是否受限必须恰好执行 K 次还是最多 K 次数组元素是否可能为 0这些细节直接决定贪心策略形态。尝试描述局部最优用一句话说清楚我每一步在选择什么。比如 122 是涨就赚55 是扩大可达边界45 是边界才结算1005 是优先翻转绝对值大的负数。判断局部最优能否推出全局最优可以通过数学归纳、交换论证或者至少手动模拟几个极端用例。想不通就换动态规划试试别硬套贪心。考虑是否需要排序如果决策对象有优先级之分比如绝对值大小、剩余步数多少排序常常是贪心的前置步骤。手推一个典型用例再写代码先用小数组把变量变化过程推一遍再写代码正确率会高很多也方便之后复习。跳出来看今天这四道题本质上是贪心的四种手感加法型贪心、覆盖型贪心、覆盖加计数型贪心、排序型贪心。贪心算法的知识点本身很浅浅到一句话就能说完但真正拉开差距的是你能不能判断这道题能不能贪。我自己的体会是判断能力没有捷径只能靠题量喂出来而且每一道题都要强迫自己说出为什么这个局部最优是安全的而不是写完 AC 就翻篇。坚持这样做一段时间再看到新题时你对该不该用贪心的第一感觉会准很多。