在力扣上刷到第1326题——Minimum Number of Taps to Open to Water a Garden中文名灌溉花园的最少水龙头数目——的时候我盯着题面看了好一会儿第一反应是这题怕不是要模拟水流扩散或者建图跑最短路。实际动手之后才发现它考的是非常经典的最少区间覆盖正解是一段不到三十行的贪心难度全在建模这一步。这篇文章把我从建模、推导、实现到踩坑的完整过程整理出来希望对正在啃hard题、或者面试前集中刷区间问题的朋友有帮助。我会把两个主流解法都写清楚讲明白每一步为什么这么做而不是只丢一个能AC的代码。1. 把浇水故事翻译成区间模型这题的hard点其实在建模1.1 原题到底在说什么先花点时间把题面还原清楚。花园是一条长度为 n 的直线坐标从 0 到 n一共有 n1 个水龙头分别放在整点位置 0、1、2、……、n 上。给你一个数组 rangesranges[i] 表示第 i 个水龙头打开之后能浇到的半径范围。也就是说位置 i 的水龙头打开以后覆盖的是闭区间 [i - ranges[i], i ranges[i]]。注意水龙头不是分布在花园两侧而是从 0 到 n 每个整数位置都有一个数组长度是 n1。要求很简单选择最少个数的水龙头打开让整段花园 [0, n] 上的每一个点都被至少一个打开的水龙头覆盖。如果做不到返回 -1。换成工程语言就是输入n花园长度ranges长度为 n1 的数组输出最少打开的水龙头数量或者 -1数据范围1 n 10^40 ranges[i] 100这里最关键的一点是浇水是连续的。虽然水龙头都在整数坐标上但它覆盖的是一整段连续区间。比如位置 3 的水龙头半径是 2覆盖 [1, 5]那么坐标 4.5 也在覆盖范围内。很多第一次做这题的人会在这一步犯迷糊把问题当成离散点覆盖想着用状态压缩或者 BFS 去硬搜。n 最大到 10^4离散化的状态空间根本没法枚举方向一开始就错了。正确的姿势是把离散的水龙头和连续的区间做一一对应。一旦完成这个对应题面里的花园、浇水、半径这些迷惑性词汇就全部退场剩下的只是一道纯区间问题。1.2 每个水龙头等价于一个区间建模这一步是整道题的灵魂。第 i 个水龙头等价于一个区间left max(0, i - ranges[i]) right min(n, i ranges[i])为什么要做 max 和 min 的裁切因为水龙头可以喷到花园外面。比如位置 0 的水龙头半径是 100理论上覆盖 [-100, 100]但花园只有 [0, n]-100 到 0 那一段完全没有意义直接截断到 0。右边同理超出 n 的部分截掉。这样处理完之后所有区间都老老实实躺在 [0, n] 内部后面排序、比较、判重都会方便很多。于是题目就变成了给定若干个区间每个区间形如 [left_i, right_i]问最少选几个区间能让它们的并集覆盖 [0, n]。这正是计算机科学里非常经典的最小区间覆盖minimum interval covering问题。用一个生活化的类比来理解想象你有一面长 n 米的墙要贴满墙纸手上有若干卷长度、起止位置各不相同的墙纸每一卷都只能从某个位置开始贴到某个位置问最少用几卷才能把整面墙贴满不能留缝。是不是一下子就熟悉了一旦你完成这个抽象hard 题的神秘感就消失了一大半。1.3 为什么它被评为 hard难的不是代码是想到说实话这道题的代码量非常小核心逻辑加起来三十行不到。它被评为困难题难点主要在三处。第一题面包装得太物理让人误以为需要处理几何、模拟水流扩散或者考虑水龙头之间互相影响。实际上水龙头之间没有任何干扰每个水龙头就是独立的一段覆盖区间想清楚这点题面就废掉了。第二区间之间可以大量重叠选择哪个重叠区间是局部最优需要你跳出逐个水龙头看的惯性站在全局维护一个已经覆盖到哪的边界。第三如果没见过最小区间覆盖这个模型很容易往 DP 甚至图论方向想。我自己第一次做的时候第一反应是这不就是个最短路吗每个水龙头是一个节点两个水龙头覆盖范围有交集就加一条边然后求从覆盖到 0 的起点到覆盖到 n 的终点的最短路径。理论上确实可以做但建图就要 O(n^2)10^4 的数据规模直接超时。后来翻讨论区才发现正解就是贪心连图都不用建。2. 贪心策略的完整推导维护湿边界和交换论证2.1 关键视角时刻记住已经湿到哪了不管你最后打开哪些水龙头成功方案覆盖出来的结果一定是从左往右连续推进的。为什么一定连续因为如果 [0, a] 和 [b, n] 都被覆盖了而 a b 中间有一段没水那花园没浇透方案直接失败。所以任何成功的方案都可以看成先用若干水龙头把 [0, x1] 浇透再用若干把 [x1, x2] 浇透一步一步推进直到覆盖到 n。每一次推进新加入的水龙头必须和已经湿掉的部分有重叠否则中间会出现干地。这个重叠条件翻译成区间语言就是新区间的左端点必须 当前已覆盖到的右边界 cur。于是问题就等价成从位置 0 出发湿边界 cur 0每次选择一个左端点 cur 的区间打开它湿边界变成 max(cur, 它的右端点)。问最少需要多少次操作能让 cur n。这一步转化非常关键。它把选哪几个区间这个组合问题变成了从 0 开始一步步往前跳的推进问题。而推进问题天然适合贪心——因为每一步只关心当前能跳多远。2.2 为什么每次选右端点最远的区间不亏标准贪心策略是把所有区间按左端点从小到大排序。维护当前已覆盖的右边界 cur。扫描所有左端点 cur 的区间记录它们右端点的最大值记为 best。如果 best cur说明没有任何区间能推进覆盖直接返回 -1。否则答案加一把 cur 更新为 best重复直到 cur n。很多人会问为什么每次一定要挑右端点最远的这里可以用交换论证exchange argument来理解。假设在某一步湿边界是 c所有左端点 c 的区间构成候选集合 S。方案 A 选了其中某个区间 I右端点是 r1方案 B 选了另一个区间 J右端点是 r2并且 r2 r1。那么把方案 A 里的 I 换成 J覆盖范围只会变大不会变小用掉的区间数量不变而且后续的候选集合也不会变小——因为新的湿边界更靠右满足左端点 湿边界条件的区间只会更多绝不会更少。换句话说选右端点最远的区间永远不亏。既然每个局部决策都存在一个最优解包含它贪心自然就是全局最优。这是区间覆盖类问题里最经典的正确性证明思路面试手撕代码的时候如果能讲出这一段加分效果很明显。再用过河踩石头类比一次你站在河边面前有几块石头有的在左前方有的在右前方你要踩石头过河当然选能让你前进最远的那一块。踩一块近的石头下一步能踩到的选择范围只会更小不会带来任何好处。2.3 无解判定为什么能放心提前退出区间按左端点排序之后扫描过程有一个很好的性质当扫描到某个位置时所有左端点 cur的区间都已经处理完了。如果在这些区间里都找不到一个能把 cur 往前推的也就是 best cur那么后面的区间左端点只会更大更不可能满足左端点 cur所以可以直接判定无解返回 -1。这个提前退出不是优化技巧而是正确性的必要部分。反例很容易构造n 5能覆盖 [0, 2] 和 [4, 5] 的区间各有一个但 (2, 4) 之间没水。推进到 2 之后后面区间的左端点是 4大于 2形成断层此时必须返回 -1而不是继续傻傻扫描。另外还有一个容易忽略的细节扫描候选区间时完全不用管这些区间彼此之间是否重叠。因为我们的目标是覆盖重叠是被允许且鼓励的这和后面要讲的选最多不重叠区间是反着的。只要每个新选区间和当前已覆盖区域有交集整体就保持连续这就够了。3. 两套实现排序贪心与 O(n) 的 rightmost 数组3.1 实现一排序后扫描区间先写出最直观的版本。把每个水龙头转成区间过滤掉退化区间排序然后一遍扫描。退化区间指的是左端点等于右端点的区间也就是半径为 0 的水龙头它只浇一个点永远不可能帮助我们推进覆盖范围直接扔掉。def minTaps(self, n: int, ranges: List[int]) - int: intervals [] for i, r in enumerate(ranges): left max(0, i - r) right min(n, i r) if right left: continue # 退化区间跳过 intervals.append((left, right)) intervals.sort(keylambda x: x[0]) # 按左端点排序 ans 0 cur 0 # 当前已经覆盖到的右边界 idx 0 m len(intervals) while idx m: best cur # 把所有左端点 cur 的区间都看一下取最大右端点 while idx m and intervals[idx][0] cur: best max(best, intervals[idx][1]) idx 1 if best cur: return -1 ans 1 cur best if cur n: return ans return -1这个版本跑通没问题时间复杂度 O(n log n)主要开销在排序。空间复杂度 O(n)。对 10^4 的数据量来说完全够用面试时写这个版本也完全可以接受。3.2 实现二用 rightmost 数组省掉排序观察一个容易被忽略的事实所有区间被裁切到 [0, n] 之后左端点的取值范围就是 0 到 n 这些整数。如果我们开一个数组 rightmost长度 n1把以 left 为左端点、能达到的最远右端点存进去那么按 left 从小到大的顺序遍历 rightmost其实就等于在遍历排好序的区间。这个思路和跳跃游戏 IIJump Game II几乎一模一样rightmost[i] 可以看成从位置 i 起跳最多能跳到的位置。跳跃游戏里每个位置天然有序所以它本身就是 O(n)这里我们只是用 rightmost 数组人为构造出了这个有序结构。def minTaps(self, n: int, ranges: List[int]) - int: rightmost [0] * (n 1) for i, r in enumerate(ranges): left max(0, i - r) right min(n, i r) if right left: rightmost[left] max(rightmost[left], right) taps 0 cur 0 farthest 0 for i in range(n 1): farthest max(farthest, rightmost[i]) if i cur: if farthest cur: # 卡住了无法推进 return -1 taps 1 cur farthest if cur n: return taps return -1整体复杂度变成 O(n) 时间和 O(n) 空间。相比排序版本少了排序的 log 因子代码也更短。这里有个细节值得多说一句for 循环必须走到 n因为位置 n 上的水龙头也可能贡献区间它的左端点可能小于 n影响前面的 rightmost 更新。3.3 用手推一遍样例确认行为符合预期拿题目自带的样例 n 5, ranges [3,4,1,1,0,0] 来走一遍水龙头 0区间 [0, 3]水龙头 1区间 [0, 5]水龙头 2区间 [1, 3]水龙头 3区间 [2, 4]水龙头 4退化区间跳过水龙头 5退化区间跳过rightmost 数组更新之后rightmost[0] max(3, 5) 5rightmost[1] 3rightmost[2] 4。模拟过程i0 时 farthest 变成 5i cur 0所以开第一个水龙头cur 更新成 5已经 n返回 1。完全符合预期——只开水龙头 1 就行。再看复杂一点的样例 n 7, ranges [1,2,1,0,2,1,0,1]水龙头 0[0, 1]水龙头 1[0, 3]水龙头 2[1, 3]水龙头 3退化水龙头 4[2, 6]水龙头 5[4, 6]水龙头 6退化水龙头 7[6, 7]rightmostrightmost[0] 3rightmost[1] 3rightmost[2] 6rightmost[4] 6rightmost[6] 7。模拟i0farthest3开第一个水龙头 1cur3i1、2 时 farthest 更新到 6i3 时 i cur开第二个水龙头 4cur6i4、5 继续更新i6 时 farthest7开第三个水龙头 7cur7达到 n返回 3。答案选中的是水龙头 1、4、7覆盖区间分别是 [0,3]、[2,6]、[6,7]无缝衔接正确。这两步手推最好自己在草稿纸上过一遍把什么时候触发开新龙头的时机吃透。特别是 i cur 的判断放在 farthest 更新之后这个顺序决定了能不能把当前格子的贡献算进去写错一个位置答案就会偏。4. 边界条件与翻车点提交三次才AC的经验4.1 坑一把 cur n 写成 cur n花园右边界是 n 本身只要覆盖到坐标 n 就算完成任务。如果写成 cur n那么当某个水龙头恰好把湿边界推到 n 时循环不会及时退出会继续多算一个水龙头。第一次我就是栽在这里一些刚好能覆盖到边界的测试用例会莫名其妙多 1WA 得很憋屈。正确的判断条件是 cur n。这属于典型的 off-by-one 错误区间题里几乎一定会遇到。排查的时候优先检查所有和边界有关的比较运算符尤其注意覆盖到端点和越过端点的区别。4.2 坑二忘记处理原地踏步导致死循环如果候选区间里没有任何一个能把 cur 往前推也就是 best cur说明从当前湿边界往后出现了一段没有任何水龙头能够到的地方。这时候必须立刻返回 -1。如果不写这个判断排序版本会陷入 while 死循环rightmost 版本会多算一个永远不会推进的假步骤最后返回错误结果或者直接超时。什么情况会出现原地踏步最简单的例子是 n 3, ranges [0,0,0,0]所有水龙头半径都是 0没有任何区间能覆盖长度大于 0 的段第一步就卡死返回 -1。另一种情况是花园中间有一截真空比如 n 5能覆盖 [0,2] 和 [4,5]但 [2,4] 之间没有任何水龙头能浇到推进到 2 之后找不到左端点 2 且右端点 2 的区间卡死。这类用例专门用来测无解判定逻辑代码里必须显式处理。4.3 坑三ranges[i] 顶到边界外必须裁切水龙头在边缘时区间会越界。位置 0 的水龙头半径 100如果不裁切左端点是 -100右端点是 100。排序版本里它似乎还能正常工作因为 left 是负数比较 intervals[idx][0] cur 时它照样满足条件。但如果你用 rightmost 数组left -100 直接数组越界崩溃。所以必须统一做 max(0, ...) 和 min(n, ...) 的裁切把区间限制在 [0, n] 内。这不仅防止数组越界也让左端点取值范围是 0 到 n这个加速前提成立。裁切本身就是建模的一部分不是可有可无的防御性代码。4.4 坑四把退化区间也存进去ranges[i] 0 的水龙头打开之后只覆盖 [i, i] 这一个点。在覆盖 [0, n] 的问题里这种区间没有任何作用如果 i 这个点已经被覆盖开它不增加任何东西如果 i 还没被覆盖开它也覆盖不了任何新的连续段。直接跳过可以少处理一堆无意义的数据。不跳过其实也不会错因为 best max(best, i) 时i 一定小于当前 cur不会真的更新边界。但代码会多处理一些无效数据排序版本里还可能干扰你对候选区间的理解。我建议显式跳过 right left 的区间代码更干净。提示判断退化区间要用 right left 而不是 right left。left 和 right 都经过裁切可能出现 left right 的情况用 更保险即使有个别区间长度为 0 也一并跳过。4.5 提交前过一遍的测试用例表建议提交前把这组用例都跑一遍覆盖正常、无解、边缘覆盖、真空带等各种情况测试场景nranges期望结果单个水龙头全覆盖5[3,4,1,1,0,0]1全部半径 0无解3[0,0,0,0]-1两段拼接8[4,0,0,0,0,0,0,0,4]2中间有真空带5[2,0,0,0,2]-1多个重叠区间推进7[1,2,1,0,2,1,0,1]3边缘水龙头覆盖全段10[10,0,0,0,0,0,0,0,0,0,0]1其中中间有真空带那个用例值得多说一句n 5位置 0 的水龙头半径 2 覆盖 [0,2]位置 5 的水龙头半径 2 覆盖 [3,5]中间 (2,3) 这半开区间没人覆盖答案必须是 -1。这种用例最考验无解判断只要它通过了基本可以放心提交。5. 举一反三从区间覆盖模板到什么时候不能贪心5.1 抽出一张通用模板把这道题再往上抽一层凡是给定一堆区间问最少选几个能覆盖目标区间 [L, R]的问题都可以套下面的贪心流程裁切把所有区间裁到 [L, R] 范围内扔掉空区间。排序按左端点升序排列。推进维护当前覆盖到的位置 pos L扫描所有左端点 pos 的区间记下最大右端点 best若 best pos 则无解否则答案加一pos best直到 pos R。这类问题的共同特征很明显区间之间允许重叠目标是覆盖一段连续区间。只要你识别出这两个特征就可以放心上贪心不需要犹豫。反过来如果题目要求的是不重叠或者最大化覆盖长度那是另一套思路别套错模板。5.2 相关题目1024、45、435 的横向对比力扣上有一道 1024. Video Stitching把视频片段 [start, end] 拼成完整 [0, time]和本题几乎同一个模型只是把水龙头换成了视频片段。做 1326 之前先做 1024 会顺很多因为那道题是中等难度建模更直白能帮你提前熟悉区间覆盖的套路。跳跃游戏 II45 题则是另一个视角的亲戚。它的数组跳跃本质就是 rightmost 版本的区间覆盖每个位置 i 能跳到的最远距离就是右端点位置本身天然有序。做完 1326 再回头看 45 题你会发现两题的代码骨架几乎可以互相套用。还要提一个常考的变式不是最少覆盖而是最多不重叠比如 435. Non-overlapping Intervals。注意这两类问题的贪心策略是完全相反的——覆盖问题按左端点排序、每次选右端点最大的不重叠问题按右端点排序、每次选结束最早的。很多面试者把这两套记混一上场就翻车。我个人的记忆方法覆盖问题是往前够所以要够得最远不重叠问题是给后面留空间所以要结束得最早。想清楚你要优化的是什么策略自然就出来了。5.3 加权重之后贪心失效该换 DP最后提醒一句这题能贪心前提是每个区间的代价相同也就是每个水龙头都算一个。如果给每个水龙头加上不同的打开成本变成最小代价覆盖贪心就不成立了。举个例子假设某个水龙头虽然能覆盖很远但打开成本是 10旁边两个短水龙头成本各是 1合起来也能覆盖同样范围且总成本更低。这时每次选最远的贪心就会选错。带权重的区间覆盖需要换成动态规划或者最短路模型那是另一个方向的 hard 题。所以做题时多问自己一句代价是均匀的吗如果是贪心如果不是老老实实 DP。我在实际刷题中的体会是1326 这道题的价值不在代码本身而在于它逼着你完成一次现实场景到区间模型的抽象。以后不管是在业务系统里做资源调度还是在算法题里遇到各种披着故事外衣的区间问题只要先想想这能不能拍平成若干个区间解题路径就会清晰很多。最后再分享一个小技巧做这类题时我的草稿纸上永远会先画一条数轴把每个区间画成一条横线眼睛能看到的断层就是代码里该返回 -1 的位置。这个习惯帮我少交了很多次错误提交也让我在讲解时能一眼跟面试官对齐思路强烈建议你也试试。 
长河君 · 2026/10/21 19:41:58 · 阅读 1.2k 灌溉花园的最少水龙头数：区间覆盖贪心建模全解析
在力扣上刷到第1326题——Minimum Number of Taps to Open to Water a Garden中文名灌溉花园的最少水龙头数目——的时候我盯着题面看了好一会儿第一反应是这题怕不是要模拟水流扩散或者建图跑最短路。实际动手之后才发现它考的是非常经典的最少区间覆盖正解是一段不到三十行的贪心难度全在建模这一步。这篇文章把我从建模、推导、实现到踩坑的完整过程整理出来希望对正在啃hard题、或者面试前集中刷区间问题的朋友有帮助。我会把两个主流解法都写清楚讲明白每一步为什么这么做而不是只丢一个能AC的代码。1. 把浇水故事翻译成区间模型这题的hard点其实在建模1.1 原题到底在说什么先花点时间把题面还原清楚。花园是一条长度为 n 的直线坐标从 0 到 n一共有 n1 个水龙头分别放在整点位置 0、1、2、……、n 上。给你一个数组 rangesranges[i] 表示第 i 个水龙头打开之后能浇到的半径范围。也就是说位置 i 的水龙头打开以后覆盖的是闭区间 [i - ranges[i], i ranges[i]]。注意水龙头不是分布在花园两侧而是从 0 到 n 每个整数位置都有一个数组长度是 n1。要求很简单选择最少个数的水龙头打开让整段花园 [0, n] 上的每一个点都被至少一个打开的水龙头覆盖。如果做不到返回 -1。换成工程语言就是输入n花园长度ranges长度为 n1 的数组输出最少打开的水龙头数量或者 -1数据范围1 n 10^40 ranges[i] 100这里最关键的一点是浇水是连续的。虽然水龙头都在整数坐标上但它覆盖的是一整段连续区间。比如位置 3 的水龙头半径是 2覆盖 [1, 5]那么坐标 4.5 也在覆盖范围内。很多第一次做这题的人会在这一步犯迷糊把问题当成离散点覆盖想着用状态压缩或者 BFS 去硬搜。n 最大到 10^4离散化的状态空间根本没法枚举方向一开始就错了。正确的姿势是把离散的水龙头和连续的区间做一一对应。一旦完成这个对应题面里的花园、浇水、半径这些迷惑性词汇就全部退场剩下的只是一道纯区间问题。1.2 每个水龙头等价于一个区间建模这一步是整道题的灵魂。第 i 个水龙头等价于一个区间left max(0, i - ranges[i]) right min(n, i ranges[i])为什么要做 max 和 min 的裁切因为水龙头可以喷到花园外面。比如位置 0 的水龙头半径是 100理论上覆盖 [-100, 100]但花园只有 [0, n]-100 到 0 那一段完全没有意义直接截断到 0。右边同理超出 n 的部分截掉。这样处理完之后所有区间都老老实实躺在 [0, n] 内部后面排序、比较、判重都会方便很多。于是题目就变成了给定若干个区间每个区间形如 [left_i, right_i]问最少选几个区间能让它们的并集覆盖 [0, n]。这正是计算机科学里非常经典的最小区间覆盖minimum interval covering问题。用一个生活化的类比来理解想象你有一面长 n 米的墙要贴满墙纸手上有若干卷长度、起止位置各不相同的墙纸每一卷都只能从某个位置开始贴到某个位置问最少用几卷才能把整面墙贴满不能留缝。是不是一下子就熟悉了一旦你完成这个抽象hard 题的神秘感就消失了一大半。1.3 为什么它被评为 hard难的不是代码是想到说实话这道题的代码量非常小核心逻辑加起来三十行不到。它被评为困难题难点主要在三处。第一题面包装得太物理让人误以为需要处理几何、模拟水流扩散或者考虑水龙头之间互相影响。实际上水龙头之间没有任何干扰每个水龙头就是独立的一段覆盖区间想清楚这点题面就废掉了。第二区间之间可以大量重叠选择哪个重叠区间是局部最优需要你跳出逐个水龙头看的惯性站在全局维护一个已经覆盖到哪的边界。第三如果没见过最小区间覆盖这个模型很容易往 DP 甚至图论方向想。我自己第一次做的时候第一反应是这不就是个最短路吗每个水龙头是一个节点两个水龙头覆盖范围有交集就加一条边然后求从覆盖到 0 的起点到覆盖到 n 的终点的最短路径。理论上确实可以做但建图就要 O(n^2)10^4 的数据规模直接超时。后来翻讨论区才发现正解就是贪心连图都不用建。2. 贪心策略的完整推导维护湿边界和交换论证2.1 关键视角时刻记住已经湿到哪了不管你最后打开哪些水龙头成功方案覆盖出来的结果一定是从左往右连续推进的。为什么一定连续因为如果 [0, a] 和 [b, n] 都被覆盖了而 a b 中间有一段没水那花园没浇透方案直接失败。所以任何成功的方案都可以看成先用若干水龙头把 [0, x1] 浇透再用若干把 [x1, x2] 浇透一步一步推进直到覆盖到 n。每一次推进新加入的水龙头必须和已经湿掉的部分有重叠否则中间会出现干地。这个重叠条件翻译成区间语言就是新区间的左端点必须 当前已覆盖到的右边界 cur。于是问题就等价成从位置 0 出发湿边界 cur 0每次选择一个左端点 cur 的区间打开它湿边界变成 max(cur, 它的右端点)。问最少需要多少次操作能让 cur n。这一步转化非常关键。它把选哪几个区间这个组合问题变成了从 0 开始一步步往前跳的推进问题。而推进问题天然适合贪心——因为每一步只关心当前能跳多远。2.2 为什么每次选右端点最远的区间不亏标准贪心策略是把所有区间按左端点从小到大排序。维护当前已覆盖的右边界 cur。扫描所有左端点 cur 的区间记录它们右端点的最大值记为 best。如果 best cur说明没有任何区间能推进覆盖直接返回 -1。否则答案加一把 cur 更新为 best重复直到 cur n。很多人会问为什么每次一定要挑右端点最远的这里可以用交换论证exchange argument来理解。假设在某一步湿边界是 c所有左端点 c 的区间构成候选集合 S。方案 A 选了其中某个区间 I右端点是 r1方案 B 选了另一个区间 J右端点是 r2并且 r2 r1。那么把方案 A 里的 I 换成 J覆盖范围只会变大不会变小用掉的区间数量不变而且后续的候选集合也不会变小——因为新的湿边界更靠右满足左端点 湿边界条件的区间只会更多绝不会更少。换句话说选右端点最远的区间永远不亏。既然每个局部决策都存在一个最优解包含它贪心自然就是全局最优。这是区间覆盖类问题里最经典的正确性证明思路面试手撕代码的时候如果能讲出这一段加分效果很明显。再用过河踩石头类比一次你站在河边面前有几块石头有的在左前方有的在右前方你要踩石头过河当然选能让你前进最远的那一块。踩一块近的石头下一步能踩到的选择范围只会更小不会带来任何好处。2.3 无解判定为什么能放心提前退出区间按左端点排序之后扫描过程有一个很好的性质当扫描到某个位置时所有左端点 cur的区间都已经处理完了。如果在这些区间里都找不到一个能把 cur 往前推的也就是 best cur那么后面的区间左端点只会更大更不可能满足左端点 cur所以可以直接判定无解返回 -1。这个提前退出不是优化技巧而是正确性的必要部分。反例很容易构造n 5能覆盖 [0, 2] 和 [4, 5] 的区间各有一个但 (2, 4) 之间没水。推进到 2 之后后面区间的左端点是 4大于 2形成断层此时必须返回 -1而不是继续傻傻扫描。另外还有一个容易忽略的细节扫描候选区间时完全不用管这些区间彼此之间是否重叠。因为我们的目标是覆盖重叠是被允许且鼓励的这和后面要讲的选最多不重叠区间是反着的。只要每个新选区间和当前已覆盖区域有交集整体就保持连续这就够了。3. 两套实现排序贪心与 O(n) 的 rightmost 数组3.1 实现一排序后扫描区间先写出最直观的版本。把每个水龙头转成区间过滤掉退化区间排序然后一遍扫描。退化区间指的是左端点等于右端点的区间也就是半径为 0 的水龙头它只浇一个点永远不可能帮助我们推进覆盖范围直接扔掉。def minTaps(self, n: int, ranges: List[int]) - int: intervals [] for i, r in enumerate(ranges): left max(0, i - r) right min(n, i r) if right left: continue # 退化区间跳过 intervals.append((left, right)) intervals.sort(keylambda x: x[0]) # 按左端点排序 ans 0 cur 0 # 当前已经覆盖到的右边界 idx 0 m len(intervals) while idx m: best cur # 把所有左端点 cur 的区间都看一下取最大右端点 while idx m and intervals[idx][0] cur: best max(best, intervals[idx][1]) idx 1 if best cur: return -1 ans 1 cur best if cur n: return ans return -1这个版本跑通没问题时间复杂度 O(n log n)主要开销在排序。空间复杂度 O(n)。对 10^4 的数据量来说完全够用面试时写这个版本也完全可以接受。3.2 实现二用 rightmost 数组省掉排序观察一个容易被忽略的事实所有区间被裁切到 [0, n] 之后左端点的取值范围就是 0 到 n 这些整数。如果我们开一个数组 rightmost长度 n1把以 left 为左端点、能达到的最远右端点存进去那么按 left 从小到大的顺序遍历 rightmost其实就等于在遍历排好序的区间。这个思路和跳跃游戏 IIJump Game II几乎一模一样rightmost[i] 可以看成从位置 i 起跳最多能跳到的位置。跳跃游戏里每个位置天然有序所以它本身就是 O(n)这里我们只是用 rightmost 数组人为构造出了这个有序结构。def minTaps(self, n: int, ranges: List[int]) - int: rightmost [0] * (n 1) for i, r in enumerate(ranges): left max(0, i - r) right min(n, i r) if right left: rightmost[left] max(rightmost[left], right) taps 0 cur 0 farthest 0 for i in range(n 1): farthest max(farthest, rightmost[i]) if i cur: if farthest cur: # 卡住了无法推进 return -1 taps 1 cur farthest if cur n: return taps return -1整体复杂度变成 O(n) 时间和 O(n) 空间。相比排序版本少了排序的 log 因子代码也更短。这里有个细节值得多说一句for 循环必须走到 n因为位置 n 上的水龙头也可能贡献区间它的左端点可能小于 n影响前面的 rightmost 更新。3.3 用手推一遍样例确认行为符合预期拿题目自带的样例 n 5, ranges [3,4,1,1,0,0] 来走一遍水龙头 0区间 [0, 3]水龙头 1区间 [0, 5]水龙头 2区间 [1, 3]水龙头 3区间 [2, 4]水龙头 4退化区间跳过水龙头 5退化区间跳过rightmost 数组更新之后rightmost[0] max(3, 5) 5rightmost[1] 3rightmost[2] 4。模拟过程i0 时 farthest 变成 5i cur 0所以开第一个水龙头cur 更新成 5已经 n返回 1。完全符合预期——只开水龙头 1 就行。再看复杂一点的样例 n 7, ranges [1,2,1,0,2,1,0,1]水龙头 0[0, 1]水龙头 1[0, 3]水龙头 2[1, 3]水龙头 3退化水龙头 4[2, 6]水龙头 5[4, 6]水龙头 6退化水龙头 7[6, 7]rightmostrightmost[0] 3rightmost[1] 3rightmost[2] 6rightmost[4] 6rightmost[6] 7。模拟i0farthest3开第一个水龙头 1cur3i1、2 时 farthest 更新到 6i3 时 i cur开第二个水龙头 4cur6i4、5 继续更新i6 时 farthest7开第三个水龙头 7cur7达到 n返回 3。答案选中的是水龙头 1、4、7覆盖区间分别是 [0,3]、[2,6]、[6,7]无缝衔接正确。这两步手推最好自己在草稿纸上过一遍把什么时候触发开新龙头的时机吃透。特别是 i cur 的判断放在 farthest 更新之后这个顺序决定了能不能把当前格子的贡献算进去写错一个位置答案就会偏。4. 边界条件与翻车点提交三次才AC的经验4.1 坑一把 cur n 写成 cur n花园右边界是 n 本身只要覆盖到坐标 n 就算完成任务。如果写成 cur n那么当某个水龙头恰好把湿边界推到 n 时循环不会及时退出会继续多算一个水龙头。第一次我就是栽在这里一些刚好能覆盖到边界的测试用例会莫名其妙多 1WA 得很憋屈。正确的判断条件是 cur n。这属于典型的 off-by-one 错误区间题里几乎一定会遇到。排查的时候优先检查所有和边界有关的比较运算符尤其注意覆盖到端点和越过端点的区别。4.2 坑二忘记处理原地踏步导致死循环如果候选区间里没有任何一个能把 cur 往前推也就是 best cur说明从当前湿边界往后出现了一段没有任何水龙头能够到的地方。这时候必须立刻返回 -1。如果不写这个判断排序版本会陷入 while 死循环rightmost 版本会多算一个永远不会推进的假步骤最后返回错误结果或者直接超时。什么情况会出现原地踏步最简单的例子是 n 3, ranges [0,0,0,0]所有水龙头半径都是 0没有任何区间能覆盖长度大于 0 的段第一步就卡死返回 -1。另一种情况是花园中间有一截真空比如 n 5能覆盖 [0,2] 和 [4,5]但 [2,4] 之间没有任何水龙头能浇到推进到 2 之后找不到左端点 2 且右端点 2 的区间卡死。这类用例专门用来测无解判定逻辑代码里必须显式处理。4.3 坑三ranges[i] 顶到边界外必须裁切水龙头在边缘时区间会越界。位置 0 的水龙头半径 100如果不裁切左端点是 -100右端点是 100。排序版本里它似乎还能正常工作因为 left 是负数比较 intervals[idx][0] cur 时它照样满足条件。但如果你用 rightmost 数组left -100 直接数组越界崩溃。所以必须统一做 max(0, ...) 和 min(n, ...) 的裁切把区间限制在 [0, n] 内。这不仅防止数组越界也让左端点取值范围是 0 到 n这个加速前提成立。裁切本身就是建模的一部分不是可有可无的防御性代码。4.4 坑四把退化区间也存进去ranges[i] 0 的水龙头打开之后只覆盖 [i, i] 这一个点。在覆盖 [0, n] 的问题里这种区间没有任何作用如果 i 这个点已经被覆盖开它不增加任何东西如果 i 还没被覆盖开它也覆盖不了任何新的连续段。直接跳过可以少处理一堆无意义的数据。不跳过其实也不会错因为 best max(best, i) 时i 一定小于当前 cur不会真的更新边界。但代码会多处理一些无效数据排序版本里还可能干扰你对候选区间的理解。我建议显式跳过 right left 的区间代码更干净。提示判断退化区间要用 right left 而不是 right left。left 和 right 都经过裁切可能出现 left right 的情况用 更保险即使有个别区间长度为 0 也一并跳过。4.5 提交前过一遍的测试用例表建议提交前把这组用例都跑一遍覆盖正常、无解、边缘覆盖、真空带等各种情况测试场景nranges期望结果单个水龙头全覆盖5[3,4,1,1,0,0]1全部半径 0无解3[0,0,0,0]-1两段拼接8[4,0,0,0,0,0,0,0,4]2中间有真空带5[2,0,0,0,2]-1多个重叠区间推进7[1,2,1,0,2,1,0,1]3边缘水龙头覆盖全段10[10,0,0,0,0,0,0,0,0,0,0]1其中中间有真空带那个用例值得多说一句n 5位置 0 的水龙头半径 2 覆盖 [0,2]位置 5 的水龙头半径 2 覆盖 [3,5]中间 (2,3) 这半开区间没人覆盖答案必须是 -1。这种用例最考验无解判断只要它通过了基本可以放心提交。5. 举一反三从区间覆盖模板到什么时候不能贪心5.1 抽出一张通用模板把这道题再往上抽一层凡是给定一堆区间问最少选几个能覆盖目标区间 [L, R]的问题都可以套下面的贪心流程裁切把所有区间裁到 [L, R] 范围内扔掉空区间。排序按左端点升序排列。推进维护当前覆盖到的位置 pos L扫描所有左端点 pos 的区间记下最大右端点 best若 best pos 则无解否则答案加一pos best直到 pos R。这类问题的共同特征很明显区间之间允许重叠目标是覆盖一段连续区间。只要你识别出这两个特征就可以放心上贪心不需要犹豫。反过来如果题目要求的是不重叠或者最大化覆盖长度那是另一套思路别套错模板。5.2 相关题目1024、45、435 的横向对比力扣上有一道 1024. Video Stitching把视频片段 [start, end] 拼成完整 [0, time]和本题几乎同一个模型只是把水龙头换成了视频片段。做 1326 之前先做 1024 会顺很多因为那道题是中等难度建模更直白能帮你提前熟悉区间覆盖的套路。跳跃游戏 II45 题则是另一个视角的亲戚。它的数组跳跃本质就是 rightmost 版本的区间覆盖每个位置 i 能跳到的最远距离就是右端点位置本身天然有序。做完 1326 再回头看 45 题你会发现两题的代码骨架几乎可以互相套用。还要提一个常考的变式不是最少覆盖而是最多不重叠比如 435. Non-overlapping Intervals。注意这两类问题的贪心策略是完全相反的——覆盖问题按左端点排序、每次选右端点最大的不重叠问题按右端点排序、每次选结束最早的。很多面试者把这两套记混一上场就翻车。我个人的记忆方法覆盖问题是往前够所以要够得最远不重叠问题是给后面留空间所以要结束得最早。想清楚你要优化的是什么策略自然就出来了。5.3 加权重之后贪心失效该换 DP最后提醒一句这题能贪心前提是每个区间的代价相同也就是每个水龙头都算一个。如果给每个水龙头加上不同的打开成本变成最小代价覆盖贪心就不成立了。举个例子假设某个水龙头虽然能覆盖很远但打开成本是 10旁边两个短水龙头成本各是 1合起来也能覆盖同样范围且总成本更低。这时每次选最远的贪心就会选错。带权重的区间覆盖需要换成动态规划或者最短路模型那是另一个方向的 hard 题。所以做题时多问自己一句代价是均匀的吗如果是贪心如果不是老老实实 DP。我在实际刷题中的体会是1326 这道题的价值不在代码本身而在于它逼着你完成一次现实场景到区间模型的抽象。以后不管是在业务系统里做资源调度还是在算法题里遇到各种披着故事外衣的区间问题只要先想想这能不能拍平成若干个区间解题路径就会清晰很多。最后再分享一个小技巧做这类题时我的草稿纸上永远会先画一条数轴把每个区间画成一条横线眼睛能看到的断层就是代码里该返回 -1 的位置。这个习惯帮我少交了很多次错误提交也让我在讲解时能一眼跟面试官对齐思路强烈建议你也试试。