训练营刷到 Day31贪心算法 Part05。到这个阶段能坚持下来的人已经不是靠新鲜感而是靠惯性。我今天不打算跟你重新背一遍贪心定义只聊这一阶段真正该掌握的区间类贪心它为什么难、为什么面试总爱考、以及怎样把一套方法用到三道高频题上。不管你是刚结束排序章节、正在刷贪心还是准备在系统设计之外补算法短板这篇内容都能直接拿来当复习提纲。区间贪心题目看着千变万化其实核心就三件事排序、维护边界、处理端点相等。这三件事搞明白了你的 Part05 基本就过关了。1. 贪心算法 Part05 到底在学什么1.1 贪心不是猜是一套可以验证的决策规则很多人对贪心算法的印象是“每一步选当前最好的”这句话没错但太笼统。真正要命的是你没法确定当前最好会不会坑了后面的选择。我举个经典例子假如硬币面值是 1 元、5 元、10 元要找 15 元贪心先拿 10 元再拿 5 元没问题可如果把硬币面值换成 1 元、5 元、11 元同样找 15 元贪心会选择 11 1 1 1 1一共 5 枚但实际上 5 5 5 只需要 3 枚。这说明什么贪心没有一个放之四海而皆准的模板你必须在具体问题里验证“局部最优能不能推出全局最优”。如果局部最优会破坏后面的可能性那这个题就不能用贪心硬解可能要换动态规划。到了训练营后期很多同学开始浮躁看到题目觉得“大概可以用贪心”就直接写循环跑过了几个用例就提交结果被隐藏用例打回来。这种挫败感其实不是因为你笨而是因为你没有建立一个判断框架。区间类贪心正好是理解这个框架最好的载体因为它的每一步决策都能在数轴上画出来验证起来非常直观。Day31 这个 Part05与其说是在教题目不如说是在逼你养成一个习惯不要只看“选什么”要看“为什么能这么选”。1.2 区间类贪心从“看感觉”到“画数轴”Part05 的题目有一个共同特点几乎全是区间题代表就是用最少数量的箭引爆气球、无重叠区间、合并区间加上偶尔出现的划分字母区间。这类题在 LeetCode 上的出现频率非常高而且它们之间高度相似。你可以把每个区间理解成一天里的一段会议目标是在同一时间只能参加一个会议的前提下参加最多的会议。这是最经典的区间调度问题答案就是按结束时间升序排序然后依次挑选开始时间不早于上一个结束时间的会议。为什么按结束时间排序而不是按开始时间因为结束时间早的会议不会占用后续太多时间当前选择给未来留下的余地最大。这是区间贪心最核心的思想做一个决策时尽量把“负面影响”控制到最小。放到题目里就是维护一个右边界然后遍历排序后的区间根据当前区间的左边界和右边界的关系做出选择。不要凭感觉猜拿笔在草稿纸上画一条数轴把区间都标上去。大部分区间题画完图之后解法就已经出来了。2. 三道必做区间题拆解从排序到 AC我按面试出现频率和题目之间的关联度选了三道题452、435、56。它们建议按这个顺序刷因为思路是递进的。452 让你理解“选点覆盖区间”435 让你理解“保留最多不重叠区间”56 让你理解“合并所有重叠区间”。这三道题做完后你对区间贪心的手感会完全不一样。2.1 用最少数量的箭引爆气球按右端点排序的经典套路452 的题目背景是平面上有一堆水平放置的气球每个气球用一个区间[xstart, xend]表示。你可以从 x 轴上的任意点垂直向上射出一支箭这支箭可以引爆所有横坐标覆盖该点的气球。问最少需要多少支箭。这个问题听起来很生活化翻译成区间语言就是给你一堆区间最少选多少个点才能让每个区间都至少包含一个点。每个区间至少要被打到一次箭的位置就是选择的点。我的解法是先把所有区间按右端点升序排序然后维护一个变量end表示当前这支箭的位置。第一支箭先射在第一个气球的右端点因为第一个气球的右端点是所有右端点里最小的这样箭能尽可能覆盖更多的后续气球。遍历剩下的区间时如果当前气球的左边界大于end说明之前这支箭已经打不到它了需要新增一支箭同时把箭的位置更新到当前气球的右端点。否则说明它可以被当前这支箭覆盖不需要新增。def findMinArrowShots(points): if not points: return 0 points.sort(keylambda p: p[1]) ans 1 end points[0][1] for start, stop in points[1:]: if start end: ans 1 end stop return ans这里最容易被忽略的是start end而不是start end。按题目的定义箭在坐标 x 处只要xstart x xend这个气球就会被引爆。所以如果前一个气球右端点是 4当前气球左端点也是 4那么箭射在 x 4 时两个气球是同时被打到的不需要新增箭。只有当前气球的左边界严格大于当前箭的位置时才新增。这道题的排序其实还有一个细节当两个区间右端点相同时谁在前面并不重要。因为我们的逻辑是拿当前区间的左边界去和上一个保留区间的右边界比较右端点相同不会影响结果。你可以把end理解为“箭当前能覆盖到的最右侧位置”只要后面的区间起点不超过这个位置就都是安全的。整体时间复杂度是排序的 O(n log n)遍历是 O(n)空间复杂度 O(1)。2.2 无重叠区间一个公式解决“最少移除”435 的题目是给一个区间集合求最少需要移除多少个区间才能让剩下的区间互不重叠。很多同学一看到“最少移除”就想模拟删除其实这是把简单问题复杂化了。最少移除的数量等于区间总数减去最多能保留的区间数量。所以这个题转换成最多能保留多少个互不重叠的区间。这就变成了我们熟悉的经典区间调度问题。解法同样是按右端点升序排序但是判断条件变成了start end。为什么是大于等于因为两个区间如果只是端点接触比如[1, 2]和[2, 3]它们并没有真正“重叠”在 435 这个题的定义里是可以同时保留的。所以当前区间的左边界只要不小于上一个被保留区间的右边界就说明它不会造成重叠可以留下。def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) keep 1 end intervals[0][1] for start, stop in intervals[1:]: if start end: keep 1 end stop return len(intervals) - keep为什么要维护keep而不是直接维护删除数量因为keep的含义是“能够保留的区间数”每次遇到一个可以保留的区间就更新右边界。最后用总数减去保留数就是需要移除的数量。如果你在遍历过程中直接数删除次数很容易搞混边界更新的时机。这里我再多说一句452 和 435 看起来很像但边界条件完全不同。452 是因为端点接触时可以被同一支箭射中435 是因为端点接触不算重叠。这两道题放一起刷就是为了让你体会到边界条件的差异有多重要。如果只背模板遇到这种细微变化必然会错。你必须回到题目定义里去确认端点接触到底算不算重叠。这也是为什么我反复强调画数轴的原因。2.3 合并区间普通区间题却总有 30% 的人踩坑56 合并区间是很多人觉得自己会做但一提交就会踩坑的题。题目要求把重叠的区间合并返回最终的区间列表。重叠的定义是[1, 4]和[4, 5]算重叠因为两端点都包含在区间内所以合并结果是[1, 5]。这道题的贪心点在于先把区间按左端点升序排序然后从左往右扫。我们维护一个结果列表res里面的最后一个区间代表“当前正在合并的区间”。每次遇到新区间时看它的左边界是否大于当前合并区间的右边界。如果大于说明它和当前合并区间没有交集可以直接加入结果列表。如果不大于说明重叠了需要把当前合并区间的右边界扩展为新旧两个右边界中更大的那个。def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [intervals[0]] for start, stop in intervals[1:]: if start res[-1][1]: res.append([start, stop]) else: res[-1][1] max(res[-1][1], stop) return res这段代码有两个特别常见的坑。第一个是用start res[-1][1]来判断是否重叠这样会把[1, 4]和[4, 5]拆成两个区间不符合题意。所以这里必须用左边界刚好等于当前右边界时也应该合并。第二个坑是有人会把合并逻辑写成res[-1][1] stop直接赋值而不是取max。比如当前合并区间是[1, 4]新来的区间是[2, 3]直接赋值为 3 会导致右边界往回缩后面的区间判断全部出错。正确做法是保留较大的右边界也就是 4因为合并后的区间要覆盖所有已经遇到的区间。从思路上看56 和 452、435 最大的区别是排序方向不同。452 和 435 按右端点排因为我们的目标是“尽量让当前区间早点结束给后面留出空间”56 按左端点排因为我们要从左往右不断扩展当前合并区间。排序方向不是随便定的它取决于你贪心的决策变量到底是什么。3. 排序、边界条件和贪心选择证明3.1 到底按左端点排还是按右端点排很多同学刷完这几道题之后会困惑下次遇到新题怎么知道按哪一端排序我提供一个非常实用的判断方法先想清楚你要维护一个什么变量再想排序方向。如果你是在做“选择”型贪心比如选最多不重叠区间、用最少的点覆盖所有区间那通常按右端点升序排序。因为右端点越小选择它给未来留下的空间越大当前选择对后续的“侵占”越少就越不容易破坏全局最优。这就像安排会议时优先参加结束早的会议而不是开始早但拖到很晚的会议。如果你是在做“扩展”型贪心比如合并区间那通常按左端点升序排序。因为合并过程中需要从左往右推进每次取一个区间和当前结果比较按左端点排序能保证我们不会漏掉任何一个新区间同时可以维护当前合并区间的最大右边界。下面这个表格可以帮你快速记忆题目场景排序方向维护变量核心原因用最少点覆盖区间右端点升序当前点位置点越靠右越能覆盖后续区间保留最多不重叠区间右端点升序上一区间右端点结束越早越容易容纳后续合并所有重叠区间左端点升序当前合并区间右端点从左到右推进逐步扩展排序方向一旦定了代码思路基本就定了一半。剩下的就是判断端点相等时到底用大于还是大于等于这个完全由题目定义决定别凭印象。3.2 那些让人崩溃的边界条件、、还是区间题的边界条件非常容易让人崩溃因为有时候多一个等号就是错。我把这三道题的边界条件汇总成一个表你刷完之后可以反复对照。题目判断条件边界含义452 引爆气球start end才新增箭端点相同时同一支箭可以同时引爆两个气球所以不需要新增435 无重叠区间start end才保留新区间端点接触不算重叠两个区间可以同时保留56 合并区间start res[-1][1]才加入新结果端点接触时两个区间连续合并后变成更大区间我见过很多人把这几道题混着背最后写出来的代码在 435 里用了在 452 里用了结果双双报错。我的建议是不要死记条件而是画数轴。当两个区间的端点重合时你只看题目问的是“能不能用一个点覆盖”如果是那就是如果问的是“算不算重叠”一般如果问的是“要不要合并”一般也是因为端点重合已经算重叠了。还有一个容易忽略的点是维护的边界变量本身。在遍历过程中边界变量的初始值是什么如果区间坐标可能是负数就不要用 0 初始化否则会把负数区间全部判错。452、435、56 这三道题里我习惯用第一个区间初始化这样最稳妥也不容易出问题。3.3 怎么说服自己“这个贪心是对的”算法题最怕的不是写不出代码而是写出来了但心里没底。尤其是贪心算法你总担心某个隐藏用例会推翻你的策略。这里我分享一个我在训练营里反复用的证明方法反证法。拿 452 举例。我们按右端点升序排序后第一支箭射在第一个气球的右端点。假设最优解的第一支箭没有射在这个位置而是射在了另一个坐标 x那么这支箭也一定在第一个气球的范围内所以 x 一定不超过第一个气球的右端点。换句话说我们把最优解的箭位置换成贪心选择的右端点并不会减少它能覆盖的气球数量因为新位置只会更靠右覆盖范围只会更大。所以贪心选择至少和最优解一样好。这就是“贪心选择性”的证明思路。435 的证明也类似。按右端点排序后第一个保留的区间是所有区间里结束最早的。假设最优解没有保留这个区间而是保留了另一个区间那我们把这个区间换成结束最早的区间对后续区间的选择不会造成任何阻碍所以结果不会变差。这类证明不要求你写得多严谨但至少要能说服自己当前这一步选择确实不会堵死后面的路。如果你能找到一个反例说明贪心会失败那就说明这个题不能贪心赶紧换思路。4. 训练营现场高频报错与排查实录4.1 常见问题速查表这几道题我见过太多人踩同样的坑。与其每次重新定位不如直接对照下面的速查表排查现象可能原因解决办法452 结果比预期多了箭用了start end端点相同时被误判为新箭改成start end452 结果比预期少了箭遍历时忘记更新end一直用旧边界判断新增箭后立即让end stop435 移除数目算错keep初始化成了 0导致计数少 1第一个区间一定是保留的初始化keep 1435 边界位置判断错用了而不是把端点接触的区间误判为重叠改成start end56 合并结果多出区间用了判断重叠导致[1,4]和[4,5]没合并改成start res[-1][1]56 合并结果右边界变小直接res[-1][1] stop没有取 max改成res[-1][1] max(res[-1][1], stop)所有区间题结果乱没排序或者排序方向选错先确认是“选择型”还是“扩展型”再定排序方向每次报错不要急着在讨论区找题解先自己拿着测试用例在纸上走一遍代码把end的变化过程写下来。区间题的本质是维护边界你只要把边界变化的每一步都搞清楚代码基本不会错。4.2 刷题心法一道题变成一类题训练营到了 Day31拼的已经不是刷题数量而是归纳能力。这三道区间题做完我希望你能形成一个条件反射看到“区间”“重叠”“最少”“覆盖”这些关键词马上想到排序和维护边界。更重要的是学会把一个题迁移到另一个题。比如划分字母字母 763题目要求把字符串划分成尽可能多的片段让每个字母只出现在一个片段中。本质上就是把每个字母第一次出现和最后一次出现的位置构造成一个区间然后做合并区间的操作。你如果理解了 56再回头看 763会发现其实就是同一个模型换了一层外壳。如果你们训练营的 Part05 题单里还有单调递增的数字这类题也不用慌。它虽然不在区间模型里但贪心的核心逻辑是一样的找到第一个破坏单调性的位置把前面的数字减一后面的全部置成 9。这种题需要的是找到“必须修正的最近位置”本质上也还是在做一个局部最优选择然后保证后续不再变坏。所以我一直觉得贪心 Part05 最适合的复习方式不是按顺序刷题而是横向比较把区间题放在一起把数字题单独归类然后问自己每个题背后的决策变量是什么。最后再分享一个小技巧。每道贪心题 AC 之后我会强迫自己写一段五十字以内的“为什么贪心是对的”再尝试写一个如果不用贪心会错的反例。这个动作我坚持了二十道题效果比再多刷五十道都明显。贪心算法最怕的不是不会做而是做对了但不知道为什么一旦题目包装换个样子你又会觉得陌生。把这些“为什么”留在笔记里下次遇到同类题判断时间会短很多信心也会稳很多。