贪心算法可能是算法面试里最“分裂”的一个话题——你说它简单吧核心思想一句话就能讲完你说它难吧LeetCode 上标着 Medium 甚至 Hard 的贪心题有时候真能把人卡到怀疑人生。我见过不少刚刷题的朋友看题解的时候觉得“就这”关上答案自己写却在“为什么这一步取局部最优最终就能得到全局最优”这个点上绕不出来。这篇 part01 不打算堆一堆题目而是把贪心算法的来龙去脉、判断标准、经典入门题的完整推导过程以及我在实际刷题中踩过的坑一次讲透。适合刚接触贪心、或者刷了十几道题还感觉“每次都是靠猜”的人。1. 贪心策略的本质每一步都做当前看起来最好的选择1.1 从生活中的小决策理解贪心先别急着看代码。你每天其实都在用贪心算法做决策——只是没意识到而已。比如你今天有 8 小时工作时间面前摆着 5 件事每件事耗时和收益都不一样。普通人的第一反应是什么先做那个“性价比最高”的也就是收益/耗时最大的。做完之后剩下的时间再重新评估继续挑性价比最高的。这个过程其实就是贪心算法。再比如说换零钱。假设有 1 元、5 元、10 元、20 元四种面额要找给顾客 67 元。大多数人的第一反应永远是先拿最大的 20 元能拿几张拿几张3 张剩下 7 元再拿 5 元1 张剩下 2 元最后拿 1 元2 张。这个“每次都尽量用最大面额”的策略也是贪心。观察这两个例子的共同点每一步的选择都只考虑当前状态下哪个选项“看起来最有利”不会为了未来某个更优结果而故意在当前让步。这就是贪心算法的核心——局部最优推导全局最优。1.2 贪心算法在算法体系中的位置算法世界里针对“求最优解”这个问题有几条不同的路。动态规划的思路是我把所有可能的状态都记下来逐步推导最终在所有方案里挑最优。回溯就更暴力了——把所有可能的路径都走一遍不行就退回来换条路。而贪心的做法最“嚣张”我不需要看完整局面也不需要记录太多历史状态每走一步就拍板拍完绝不回头。举个例子假设你要从 A 地走到 B 地中间要经过好几个中转点回溯把 A 到 B 之间每一条路都走一遍记录最短的那条。动态规划从 B 往前倒推站在每个中转点上都知道“从这里到终点最短还要多远”然后选一条最短的。贪心站在 A 点只往后看一步选一条看起来离 B 最近的航线走了再说。我以前总觉得贪心是动态规划的一种“偷懒版”。这个理解不准确。贪心确实可以看成动态规划的退化形式——动态规划需要计算所有子问题然后取最优贪心只做一次选择——但贪心能成立的条件很苛刻并不是所有动态规划题都能“省成”贪心。反过来能用贪心的题往往都有非常明显的结构特征识别这个特征比多背几十道题管用得多。1.3 为什么贪心策略行得通无后效性贪心敢于“不回头”背后靠的是一个性质——叫无后效性。无后效性指的是当前状态一旦确定之后的过程就不会再受之前状态的影响未来只和“现在站在哪里”有关跟“怎么走到这里的”无关。就像下棋如果每一步的走法只取决于当前棋盘的局势而不取决于之前具体走了哪几步那这个系统就具备无后效性。贪心算法每一步决策时其实隐含了一个假设当前这一步选完之后接下来面对的局面和“我接下来从当前局面继续走”完全等价之前的选择不会干扰后面的决策空间。换句话说当前局部最优的选择不会让未来的某个更优选择变得不可达。这就是为什么贪心能“拍脑袋拍得理直气壮”——因为性质决定了你这步拍完后面的问题还是一个同样结构的新问题只是规模小了一点而已。2. 贪心算法适用的两个关键特征贪心选择性质与最优子结构很多人学贪心感觉很虚就是因为只记住了“局部最优推导全局最优”这句话却没搞明白什么时候能这么推导什么时候推导不出来。判断一道题能不能用贪心核心就两条。2.1 特征一贪心选择性质所谓贪心选择性质就是——原问题的最优解可以通过做出一系列贪心选择来获得。翻译成人话存在一个“贪心策略”你按这个策略一步步选选出来的结果就是全局最优解。听起来像废话。真正有用的问题是怎么判断一个策略具备这个性质常见的做法是数学归纳法证明。以“选最小的那个元素”这种策略为例你需要证明两点存在一个全局最优解包含了贪心策略选出的第一个元素。做出第一个贪心选择后剩余子问题的最优解加上第一个选择就是原问题的最优解。第一点说的是“第一个选择不会错过最优解”第二点说的是“选完之后剩下的问题仍然能用同样的方法解”。实际操作中我很少真的去写严格证明但我一定会做一件事——在脑海里构造反例。如果构造了半天都找不到反例那这道题大概率能贪心如果很容易就找到一个反例那就赶紧转去动态规划。2.2 特征二最优子结构最优子结构这个概念学过动态规划的人应该很熟。它指的是一个问题的最优解包含了其子问题的最优解。放在贪心语境下意味着你每一步做的局部选择所剩下来的子问题它本身也要能通过同样的贪心策略得到最优解。这两个特征其实是配套的。贪心选择性质保证了“第一步选对了”最优子结构保证了“接下来每一步照着这个套路走都选得对”。于是整体上贪心策略就像一个永远正确的公式从头套到尾。2.3 一个经典的反例为什么有的题看着能贪心却不行光说理论太干。我拿一个经典的“坑爹题”来说明判断标准怎么用——0-1 背包问题。假设背包容量 10有三件物品物品重量价值性价比价值/重量A6122.0B591.8C591.8如果按性价比排序肯定先拿 A——A 的性价比最高。拿完 A 之后背包还剩 4 容量B 和 C 都放不下了总价值 12。但最优解是什么是拿 B 和 C总重量 10正好把背包装满总价值 18。看见没第一步贪心选择 A 这个“局部最优”举动直接把最优解给断送了。为什么因为 0-1 背包问题的约束是“每件物品只能整件取”你取 A 之后剩下的容量不足以容纳任何其他物品而 BC 的组合虽然第一步看起来“性价比低”却在全局上胜出。对比一下另一个变体——分数背包物品可以切开只拿一部分。这时候按性价比排序就没问题先拿 A 的绝大部分剩余容量装 B 的一部分总价值一定最优。为什么因为物品可分割切开了不产生“剩余容量浪费”贪心选择的每一步都不会堵死后续的更优选择。这个例子可以帮助理解贪心和动态规划的边界当你的选择会显著改变后续可选空间并且这种改变可能让你错失全局最优时贪心就大概率不成立。而动态规划之所以在背包问题里永远可靠是因为它把所有剩余容量对应的状态都算了一遍不存在“拍板后不回头”的问题。刷题多了之后你会发现凡是能用贪心的题背后的决策空间通常有某种“单调性”或“可交换性”——你先选 A 再选 B和先选 B 再选 A最终结果不变。这类结构才撑得起贪心策略。3. 三道 LeetCode 入门题实战拆解从思路到 AC接下来进入实战环节。我挑了 LeetCode 上贪心专题最经典的三道初级题455 分发饼干、376 摆动序列、53 最大子序和。这三道题分别代表了贪心在“匹配类”、“序列类”、“连续区间类”问题里的典型用法而且每道的贪心策略推导过程都很有代表性值得一步一步看。3.1 LeetCode 455 分发饼干排序 双指针解决匹配问题题目大意有一群孩子每个孩子 i 的胃口是g[i]有一堆饼干每块饼干 j 的大小是s[j]。饼干 j 能喂饱孩子 i 当且仅当s[j] g[i]。每个孩子最多给一块饼干每块饼干也只能给一个孩子。问你最多能喂饱几个孩子。这道题一眼看上去很简单但第一次做的人常见的错误是——先拿最大的饼干去喂胃口最大的孩子也就是从后往前匹配。这其实也能做但我更推荐另一个方向的策略。贪心策略先把孩子的胃口和饼干大小都升序排列然后用一个指针指孩子一个指针指饼干。每次拿“当前最小的一块饼干”去喂“当前胃口最小的孩子”如果这块饼干能满足这个孩子两个指针同时后移答案加 1。如果满足不了说明这块饼干太小了谁都喂不饱因为当前孩子是胃口最小的最小的都喂不饱后面的更喂不饱直接丢弃这块饼干饼干指针后移。为什么局部最优能推出全局最优这个策略的贪心逻辑在于——“当前最小饼干如果能喂当前最小胃口的孩子那用它来喂是最不浪费的如果连最小饼干都喂不了最小胃口的孩子那它对于任何孩子都没用直接丢掉”。每一步都在做“用最恰当的饼干匹配最恰当的孩子”剩余的饼干和孩子仍然是同样结构的问题所以最终能得到最多匹配数量。C 代码实现class Solution { public: int findContentChildren(vectorint g, vectorint s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int child 0, cookie 0; while (child g.size() cookie s.size()) { if (s[cookie] g[child]) { child; } cookie; } return child; } };如果按 Python 写逻辑一模一样class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() i, j 0, 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i实现上有个容易绕晕的细节cookie没有写在else里而是每次循环都执行。这意味着“饼干指针”永远在前进要么是“喂掉了当前孩子所以前进”要么是“饼干太小直接丢弃所以前进”。而child只有喂饱的时候才前进。最后返回child就是喂饱个数。复杂度排序 O(n log n)双指针扫描 O(n)整体 O(n log n)。空间复杂度 O(1)。我踩过的坑刚开始写的时候喜欢把“饼干从小到大”换成“饼干从大到小”也就是先用大饼干喂大孩子。逻辑上同样正确但代码里需要两个指针分别从尾部走还要处理下标越界问题容易多想一步。建议初学者固定从小往大写思路最直。另外注意题目输入里g或s可能是空的循环条件写好了就不会越界不用额外 if。3.2 LeetCode 376 摆动序列删中间值还是留峰谷题目大意给你一个整数数组nums要求找出最长的“摆动子序列”长度。所谓“摆动序列”就是相邻元素的差值正负交替——比如[1,7,4,9,2,5]就满足7-1 为正4-7 为负9-4 为正2-9 为负5-2 为正。而[1,4,7,2,5]就不满足因为 4-1 正、7-4 还是正没有交替。题目本质你可以通过删除一些元素来让剩下的序列变成摆动序列。注意不是连续子数组是子序列。问最长能保多长。第一反应可能是动态规划——确实能解但贪心也能解而且代码很简短。贪心策略默认情况一个元素自身就是一个长度为 1 的摆动序列。从第二个元素开始逐个计算相邻差值nums[i] - nums[i-1]。记录“上一次的正负趋势”如果当前差值和上次趋势相反说明出现了新的“摆动”答案加 1如果相同或者是零说明当前这个点在一个单调延伸的区间内部它不贡献新的摆动。更直观的理解方式想象股票价格的折线图。一段单调上升段里起点和终点是整段里最有价值的位置——终点比起点高而且终点同时是“趋势反转的拐点”。中间那些点既没有比终点高又没有改变方向删掉它们对整体没有任何损失。贪心在这里做的事情就是——只保留趋势发生反转的拐点其余一律不要。用up和down两个变量会更简洁class Solution: def wiggleMaxLength(self, nums: List[int]) - int: n len(nums) if n 2: return n up 1 down 1 for i in range(1, n): if nums[i] nums[i-1]: up down 1 elif nums[i] nums[i-1]: down up 1 return max(up, down)这个解法的核心是状态转移而不是直接比较差值符号。up表示“以当前元素结尾并且最后一段趋势是上升”的最长摆动序列长度down表示最后一段是下降的最长摆长。当nums[i] nums[i-1]时说明可以在一个末尾下降的摆动序列后面接上这个上升段所以up down 1反过来同理。C 版本class Solution { public: int wiggleMaxLength(vectorint nums) { int n nums.size(); if (n 2) return n; int up 1, down 1; for (int i 1; i n; i) { if (nums[i] nums[i - 1]) { up down 1; } else if (nums[i] nums[i - 1]) { down up 1; } } return max(up, down); } };初学的时候可能会有疑问up down 1为什么不是up up 1很简单想要接上一个上升段前面必须是下降趋势结尾的序列才行。如果前面已经是上升趋势了直接接上升段并不会新增一个摆动的转折点。这个“状态交替”的逻辑和斐波那契式的递推还不太一样建议自己拿几个例子手推一遍。做题心得这道题我一开始就是老老实实扫描差值存到数组里再遍历找正负交替几次。能过但代码长、边界多。后来看了状态机思路才知道所谓“贪心选择”就是只保留拐点而up和down的交替更新天然就实现了这个逻辑。刷题到后面你会发现很多数组题的“最优写法”其实都是从一个更数学化的视角压缩出来的。3.3 LeetCode 53 最大子序和局部最优怎么准确传导题目大意给你一个整数数组nums找一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。这是贪心算法中另一类经典题型——连续区间最值。我第一次学动态规划的时候也写过这道题用dp[i]表示以nums[i]结尾的最大子序和dp[i] max(dp[i-1] nums[i], nums[i])然后取整个 dp 数组的最大值。其实贪心版本的思路和这个动态规划几乎是一一对应的。贪心策略遍历数组维护一个current_sum表示“以当前元素结尾的连续子数组的和”。如果当前和是负数说明它对后续没有贡献直接丢弃从当前元素重新开始累计如果当前和是正数就保留它继续往后累加。同时维护一个全局的max_sum实时记录下出现过的最大的current_sum。class Solution: def maxSubArray(self, nums: List[int]) - int: current_sum 0 max_sum nums[0] for num in nums: current_sum max(current_sum num, num) max_sum max(max_sum, current_sum) return max_sumC 写法class Solution { public: int maxSubArray(vectorint nums) { int currentSum 0; int maxSum nums[0]; for (int num : nums) { currentSum max(currentSum num, num); maxSum max(maxSum, currentSum); } return maxSum; } };核心逻辑其实只有一个关键点current_sum max(current_sum num, num)。这个 max 的语义是——如果之前累积的和是负数那么 “之前和 当前元素” 一定小于 “单独拿当前元素”所以不如直接从当前元素重新开始。这一步体现的正是贪心的“局部最优决策”负数的前缀和不应该被保留。为什么局部最优在全局成立因为最大子序和必然以某个位置 i 结尾。如果存在某个以 i 结尾的子数组 [j..i]它的前缀 [j..k] (k i) 的和是负数那你把这段前缀删掉剩下的 [k1..i] 和一定更大于原数组而且仍然是连续子数组。既然更优那么最优解里一定不包含这些“负前缀”。所以每次把负的 current_sum 清零并不会丢掉任何可能构成全局最优解的候选。这也是贪心和动态规划结合最紧密的一道题动态规划的状态转移方程写出来之后你会发现它本质上就是在做局部最优决策。所以这道题很适合用来理解“为什么有些题既能归到 DP 又能归到贪心”——它们的边界本来就模糊。几点补充max_sum初始值不能设成 0否则数组全为负数时结果会错误地返回 0而不是最大的那个负数。题目如果允许返回子数组本身而不只是最大值就需要额外记录起止下标此时贪心代码要稍微改造——每次current_sum被重置时记录新的起点。这道题有个进阶版本要求你同时输出最大和对应的区间边界做法是维护temp_start、final_start、final_end三个变量逻辑也不难这里不展开了有兴趣可以自己练练。4. 贪心策略在更复杂场景中的变体区间问题与活动选择很多人觉得贪心只能用来做“入门题”这是对贪心最大的误解。工程里真正大量使用贪心的地方其实是区间类问题——会议排期、资源调度、任务分配全都是贪心算法的活跃领域。而且算法竞赛里有一整类“区间贪心”题思路完全不同于数组题。这里我挑一个最经典的方向讲讲最大不重叠区间数以及它背后的“活动选择问题”。4.1 活动选择问题为什么按结束时间排是最优活动选择问题的描述是你有一个会议室收到了 n 个活动的申请每个活动有开始时间start[i]和结束时间end[i]。同一时间只能安排一个活动问最多能安排多少个活动。这个问题的贪心策略特别经典按结束时间从小到大排序每次选择结束时间最早且和之前已选活动不冲突的活动。为什么这个策略是对的核心逻辑是对于第一个活动如果某个最优解中首先安排的不是结束时间最早的那个活动 A而是另一个活动 BB 的结束时间晚于 A那我们完全可以把 B 替换成 A。因为 A 的结束时间更早替换后剩下的时间窗口只会更宽松不会让后面的活动变得更难安排。这样我们就证明了存在一个最优解它包含结束时间最早的活动。接下来对剩余区间做同样的推理就得到了整体最优解。之前我提到“可交换性”——这个题就是最典型的例子。替换 B 为 A 之后原最优解中的其他活动依然可以保持原样安排不会产生冲突。这种“任意最优解都能替换成包含贪心选择的形式”的论证就是贪心正确性证明里最常见的结构。4.2 求重叠区间数本质是贪心思想的延伸LeetCode 上有个很经典的题叫435 无重叠区间——给定一个区间集合让你移除最少数量的区间使得剩下的区间互不重叠。它和活动选择问题互为镜像。换个角度理解要移除最少就是保留最多不重叠区间。所以这题完全可以套上活动选择问题的解法——按结束时间排序贪心地保留尽量多的不重叠区间然后用总数量减掉保留数量就是需要移除的数量。class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: intervals.sort(keylambda x: x[1]) keep 1 prev_end intervals[0][1] for start, end in intervals[1:]: if start prev_end: keep 1 prev_end end return len(intervals) - keep边界判断注意start prev_end算不重叠端点可以相接。如果题目改成“端点不能重叠”就把改成。这类题为什么值得单独一提因为我看过不少教程讲到贪心就停留在“排序 遍历”这种笼统归纳结果很多人遇到区间题就发怵该按左端点排还是右端点排遇到冲突该留哪个其实只要抓住“活动选择”这个母题绝大多数区间调度问题都会归到同一条思路上来。后面 part02 如果讲区间专题我再展开更复杂的区间合并、区间分组、区间覆盖这些变体。5. 一个容易翻车的点贪心策略的正确性不能靠“感觉”5.1 你以为的贪心和题解里的贪心差在证明我见过太多人刷贪心题的状态看懂一题觉得自己懂了换一道同类型的又不会了。这背后最大的问题是把“记住策略”当成了“理解策略”。你记住了“按结束时间排序”还是“按开始时间排序”但题目改了一个条件你可能就懵了。举一个我印象很深的例子——跳跃游戏 IILeetCode 45它的贪心策略不是“每次跳最远”而是“在当前能到达的范围内选择一个位置使得从该位置能延伸到的最远边界最大”。这两种策略在部分样例上结果一样但在很多用例上不一样。网上甚至有段子说这道题是“贪心还是 BFS”之争。如果只看结论你会觉得“每次选能跳最远的那个点”就够了。但严格来说正确的贪心策略比这精细一点点class Solution: def jump(self, nums: List[int]) - int: n len(nums) if n 2: return 0 steps 0 current_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: steps 1 current_end farthest return steps这段代码的核心是分层次地更新右边界。current_end是当前步数能到达的最远距离当遍历到达这个边界时说明必须多走一步同时把边界扩展到farthest所有已经扫过的位置里能跳到的最远距离。整个过程更像 BFS 的层序遍历。如果你只是简单地维护一个“当前能跳多远的最大值”在某些测试用例下会出错。我觉得这个例子很好地说明了贪心策略不是“拍脑袋抄一个最像的做法”而是来自对问题结构的准确理解。5.2 用反例测试自己的策略分享一个我在实际写题中很管用的自查方法写一个暴力解法或者直接用动态规划作为参照再写一个贪心解法然后用随机数据对拍。比如拿到一道题你觉得应该是贪心先花十分钟写一个简单的暴力回溯版数据量小的时候完全能跑再写贪心版。随机生成几千组小规模测试数据分别跑两边只要结果不一致立刻定位到反例分析为什么贪心在这个反例上挂了。这个过程往往比看十篇题解都有效。我以前觉得对拍是竞赛选手才做的事工作以后才发现这是最强的“验算法”手段。特别是贪心这种“看着对但其实错”的算法没有对拍你可能带着错误策略刷几十道题都不自知。6. 从刷题到应用贪心思维在真实系统里的落脚点聊了不少题目很多读者可能会问贪心算法在公司里真的用得到吗说实话除非你在做算法岗或者基础架构否则几乎不会有人在生产代码里手写一个“区间调度贪心”。但贪心思想在企业级应用里比算法题里的出现频率高得多。举几个例子负载均衡中的最少连接算法Nginx 的负载均衡策略里有一种叫 least_conn——新请求转发给当前活跃连接数最少的后端服务。这就是个贪心决策我们希望整体负载尽量均衡那每个新请求都选择当前最空闲的机器从局部看是最优的。这个策略在大多数场景下工作得很好但它不保证全局最优——比如某个后端服务响应极慢连接数虽然少但每个连接都占用很长时间这时候贪心选它反而可能加剧问题。缓存淘汰策略LRU 缓存淘汰算法本质上是一种基于“历史访问模式”的预测但像 LFU最少使用频率的某些变体在访问模式切换时也会用贪心的思路做决策。更直接的例子是缓存系统中的 Greedy Dual Size 算法它每次淘汰时选择“代价最小的对象”这也是贪心。网络路由中的最短路径Dijkstra 算法本身就是一种贪心——每次从未处理的节点中选距离最小的作为确定的最短路径。它的正确性基于“非负权边”这个前提。一旦有负权边贪心就失效这就是为什么会有 Bellman-Ford 算法存在。任务调度系统很多定时任务系统里任务按截止时间排序优先调度 deadline 最近的任务这就是 EDFEarliest Deadline First调度策略一个非常典型的贪心应用。在 CPU 调度、实时系统里这类策略几乎是标配。扯这些是想说一个观点贪心算法不是刷题专用的小技巧它是一整套“在信息有限、计算资源有限的情况下做快速决策”的思考方式。你真正需要训练的能力不是背下几十个策略而是看到一个决策问题能快速判断出“这里是否适合用贪心”“如果要证明它是对的我应该从哪里下手”。我在带团队做技术方案评审时经常遇到同事给出一个启发式方案说“这个应该是最优的”。我一般不会直接说不对而是会问一个问题你能不能给出一个反例如果一时间给不出反例那这个方案至少值得一试如果反例很容易构造那就说明方案的路子有问题需要再往深处想想。这个方法对算法题同样适用——判断你的贪心策略成不成立最快的方式就是试图制造反例。7. 贪心算法的工程落地什么时候“差不多最优”就够用了最后想认真聊聊“最优”这两个字。我在实际工程项目里遇到大量场景严格意义上的最优解是求不出来的——要么计算量太大NP-Hard要么信息不全要么状态空间爆炸。这种时候工程的常规操作不是硬上精确解而是退而求其次用近似算法而贪心是设计近似算法时最常用的基础手段。比如多机调度问题有 m 台机器n 个任务每个任务耗时不同问怎么分配让所有任务完成的时间最短。这个问题是 NP-Hard但有一个非常著名的近似算法叫 LPT 规则Longest Processing Time first——按处理时间从大到小排序依次把每个任务分配给当前负载最小的机器。这个算法永远能给出不超过最优解 4/3 倍的调度方案。这个结论是由数学保证的工程上用起来心里有底。再比如集合覆盖问题给定全集和若干子集挑最少的子集覆盖所有元素。这也是 NP-Hard经典近似算法是贪心——每次选能覆盖最多“还没覆盖元素”的子集。贪心给出的解最多比最优解多 O(log n) 倍。很多基站选址、传感器布置问题的工程解法本质就是这个贪心近似。所以我的建议是学贪心的时候别把它当成“只能应付面试的玩具”。当你把它放进“近似算法”的大框架里去理解你会发现它是处理真实世界复杂问题时最好用的那批工具之一。精确解当然是美好的但工程上“足够好且能算得快”往往是更现实的目标。8. 这一篇的收尾把贪心当成一个思考习惯有个段子说贪心算法就是“每次选择看起来最好的然后期待全局最好”——听起来像赌徒逻辑但实际上真正成立的贪心策略背后都有严格的数学性质支撑。这就是为什么我觉得学贪心最推荐的路径不是狂刷题而是先弄懂“判据”拿到一个问题先看是否存在“贪心选择性质”——即把第一个最优选择替换成贪心选择不会损害全局最优性。再看“最优子结构”——全局最优能否由子问题最优组合而成。如果一个贪心策略满足这两条就可以放心写代码。如果不确定先写个暴力对拍验证。我刷了这么多年题最有价值的习惯就是从“看着这个题像贪心”进化到“我能说明白了为什么这个题必须是贪心”。这个进化过程很花时间但一旦建立起来后续接触区间问题、哈夫曼编码、最小生成树、Dijkstra 这些经典贪心应用时会顺畅得离谱。这篇 part01 先讲到这里。下一篇我打算把贪心在区间问题里的各种变体合并区间、分组、覆盖、单调栈和贪心配合的题目以及常见反例做一个系统性梳理。如果你看完这篇最大的收获不是记住了三道题的解法而是终于搞清楚“为什么这道题敢用贪心”那我觉得这一篇就没白写。我在实际写代码中还有一个体会顺带分享一下贪心算法的代码往往不长但 test case 边界经常坑人——空数组、全负数、重复元素、极端大数——每一个都可能让你的“最优策略”直接穿上隐身衣。写完代码之后把自己的输入变量在脑子里快速过一遍极值场景比多跑几个样例有用得多。