企业官网建设流程全解析

LeetCode 贪婪策略专项：覆盖类“最少区间数”问题的统一套路（跳跃游戏 II / 视频拼接 / 灌溉水龙头）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

贪婪（Greedy）策略是算法面试中最常见的思想之一，而“覆盖类问题”是其中套路最统一、最容易举一反三的题型。本文以 thinkings/greedy.en.md（中文原版见 thinkings/greedy.md）为核心，系统讲解贪婪策略的核心概念与适用条件，并选取 LeetCode 上三道典型的覆盖问题——45. 跳跃游戏 II、1024. 视频拼接、1326. 灌溉花园的最少水龙头数目——逐题拆解，带你吃透“维护最右可达边界 + 触界计数”这一通用模板。读完本文，你将能用一套代码骨架秒解三类表面不同、底层一致的覆盖类题目，并理解贪心与动态规划在极值问题上的取舍关系。

贪婪策略：局部最优与无后效性

贪婪策略是一种常见的算法思想。具体是指，在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。

贪心算法并不是对所有问题都能得到整体最优解，一个经典的反例是硬币找零问题：当硬币面额不满足倍数关系时，一味选择最大面额可能得不到最少硬币数。因此，关键是贪心策略的选择。

要保证贪心策略成立，所选的策略必须满足无后效性：

• 即某个状态以前的过程不会影响以后的状态；
• 当前决策只与当前状态有关，与之前如何到达该状态无关。

这一点与动态规划是相同的。事实上，贪婪策略和动态规划非常相似，大多数情况下都是用来处理极值问题（求最大、最小、最多、最少）。

从源码结构看，本仓库的 thinkings/dynamic-programming.en.md 与 thinkings/greedy.en.md 同属算法思想专题，二者在讲解上互为补充：极值问题既可以用 DP 精确求解，也可以用贪心快速求解，区别在于贪心需要额外证明“局部最优即全局最优”。

覆盖问题的统一抽象模型

LeetCode 上关于贪婪策略有 70 余道题目，本文聚焦其中套路最固定的一类——覆盖问题。除贪婪法外，这三道题也都可以用动态规划求解。

覆盖问题的一大特征，可以抽象为：

给定数轴上的一个大区间 I 和 n 个小区间 i[0], i[1], ..., i[n - 1]，问最少选择多少个小区间，使得这些小区间的并集可以覆盖整个大区间。

我们挑选三道题来讲解：

• 45. 跳跃游戏 II（困难）
• 1024. 视频拼接（中等）
• 1326. 灌溉花园的最少水龙头数目（困难）

下面逐一拆解。

45. 跳跃游戏 II：从“可跳范围”到“最右边界”

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。

思路：每次在可跳范围内选择跳得更远的位置

这里使用贪婪策略求解：每次都在当前可跳范围内，选择能跳得更远的位置。

以输入[2,3,1,1,4]为例：

• 起始位置下标 0 的值为 2，可跳范围为下标 1、2 两个位置。由于下标 1 处的 3 可以跳得更远，足以覆盖下标 2 处的情况，因此第一步应跳到下标 1。
• 跳到下标 1 后，可跳范围为下标 2、3、4（值为 1、1、4）。由于下标 4 处的 4 可以跳得更远，因此第二步直接跳到最后一个位置，共 2 次跳跃。

写成代码时，用两个关键变量维护：

• end：当前这一“跳”所能到达的边界（即当前可跳范围的最右端）；
• furthest：遍历过程中实时更新的、从当前边界内任意位置出发能到达的最远下标。

遍历数组时，一旦i == end，说明这一跳覆盖的范围已经走完，必须发起下一次跳跃：cnt += 1，并把end更新为furthest。

代码

代码支持：Python3

class Solution: def jump(self, nums: List[int]) -> int: n, cnt, furthest, end = len(nums), 0, 0, 0 for i in range(n - 1): # 更新从当前位置能跳到的最远位置 furthest = max(furthest, nums[i] + i) # 到达本次跳跃的边界，必须再跳一次 if i == end: cnt += 1 end = furthest return cnt

复杂度分析

• 时间复杂度：$O(N)$，只需一次线性遍历。
• 空间复杂度：$O(1)$，仅用常数个变量。

仓库佐证：55. 跳跃游戏是它的“初级版”

本仓库的 problems/55.jump-game.md 正是本题的初级版本：只判断“能否到达最后一个位置”，而不是求“最少跳跃次数”。该文档明确写道“我在贪心的专题中，讲到了这道题的升级版”，其核心思路也是“用一个变量记录当前能够到达的最大的索引，并逐个遍历数组中的元素去更新这个索引”，代码维护的max变量即对应本文的furthest。两道题共享同一个贪心内核，仅目标不同——初级版求布尔可达性，升级版求最少步数，二者的状态转移完全同构。

1024. 视频拼接：二维区间如何“降维”成跳跃游戏

题目描述

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。 视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1。 示例 1： 输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 输出：3 解释：我们选中 [0,2], [8,10], [1,9] 这三个片段。 将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9]。 现在我们手上有 [0,2] + [2,8] + [8,10]，这些涵盖了整场比赛 [0, 10]。 示例 2： 输入：clips = [[0,1],[1,2]], T = 5 输出：-1 解释：我们无法只用 [0,1] 和 [0,2] 覆盖 [0,5] 的整个过程。 示例 3： 输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 输出：3 解释：我们选取片段 [0,4], [4,7] 和 [6,9]。 示例 4： 输入：clips = [[0,4],[2,8]], T = 5 输出：2 解释：注意，你可能录制超过比赛结束时间的视频。 提示： 1 <= clips.length <= 100 0 <= clips[i][0], clips[i][1] <= 100 0 <= T <= 100

思路：桶思想预处理，把区间数组改写成“跳跃能力”数组

上一题的思路是维护furthest、end两个变量并不断贪心更新，本题完全沿用同一套路，区别只在于本题的数据是二维区间数组。

关键洞察在于如何把区间数据改写成与跳跃游戏同构的形式。以示例 3 的数据为例：

clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9

按开始时间排序后，只看前面一部分：

[[0,1], [0,2], [0,3], [0,4], [1,3], [1,4], [2,5], [2,6], ...]

注意：并不需要真正排序，而是采用类似桶排序的思路，使用额外空间完成等价预处理（具体见代码）。观察发现，从起点 0 出发，最多可以一步覆盖到位置 4（片段 [0,4]）；这与跳跃游戏中“位置 0 的跳跃能力为 4”完全等价。因此该输入可以改写成跳跃游戏视角下的[4,0,2]形式——至此，这道题被成功转换为上一题。

与上一题唯一的不同是：跳跃游戏保证可以跳到最后，而本题可能拼不出来，因此需要增加一个临界值判断：当last == i（当前最右可达位置没能超过当前位置）时，说明出现了无法覆盖的断裂点，直接返回-1。

代码

代码支持：Python3

class Solution: def videoStitching(self, clips: List[List[int]], T: int) -> int: # furthest[i] 表示：覆盖到点 i 时，能同时覆盖到的最右位置 furthest = [0] * (T) for s, e in clips: for i in range(s, e + 1): # 超出 T 的部分无需考虑， # 这也是可以建立一个大小为 T 的 furthest 数组的原因 if i >= T: break furthest[i] = max(furthest[i], e) # 经过上面的预处理，本题与上一题的差距已经很小 # 这里的 last 相当于上一题的 furthest end = last = ans = 0 for i in range(T): last = max(last, furthest[i]) # 比上一题多出的临界值判断： # 最右可达位置无法超过当前位置，说明存在覆盖不到的断点 if last == i: return -1 if end == i: ans += 1 end = last return ans

复杂度分析

• 时间复杂度：$O(\sum_{i=1}^{n}ranges[i] + T)$，其中ranges[i]为clips[i]的区间长度；预处理部分对每个片段遍历其区间内每个整数点，主循环再线性扫一遍T。
• 空间复杂度：$O(T)$，用于furthest数组。

1326. 灌溉花园的最少水龙头数目：n + 1 个圆覆盖一条线段

题目描述

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。 花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n]。 给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges，其中 ranges[i]（下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]]。 请你返回可以灌溉整个花园的最少水龙头数目。如果花园始终存在无法灌溉到的地方，请你返回 -1。 示例 1： 输入：n = 5, ranges = [3,4,1,1,0,0] 输出：1 解释： 点 0 处的水龙头可以灌溉区间 [-3,3] 点 1 处的水龙头可以灌溉区间 [-3,5] 点 2 处的水龙头可以灌溉区间 [1,3] 点 3 处的水龙头可以灌溉区间 [2,4] 点 4 处的水龙头可以灌溉区间 [4,4] 点 5 处的水龙头可以灌溉区间 [5,5] 只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5]。 示例 2： 输入：n = 3, ranges = [0,0,0,0] 输出：-1 解释：即使打开所有水龙头，你也无法灌溉整个花园。 示例 3： 输入：n = 7, ranges = [1,2,1,0,2,1,0,1] 输出：3 示例 4： 输入：n = 8, ranges = [4,0,0,0,0,0,0,0,4] 输出：2 示例 5： 输入：n = 8, ranges = [4,0,0,0,4,0,0,0,4] 输出：1 提示： 1 <= n <= 10^4 ranges.length == n + 1 0 <= ranges[i] <= 100

思路：与上一题几乎一模一样的算法

本题思路与 1024 题完全一致：仍然采用贪心策略，尽量找到能够覆盖最远（最右）位置的水龙头，并记录它最右覆盖到的土地。算法分三步：

1. 使用furthest[i]记录经过预处理后、能够覆盖点i的所有水龙头中最靠右的覆盖位置。一共有n + 1个水龙头，逐个遍历，每个水龙头覆盖区间为[i - ranges[i], i + ranges[i]]（需裁剪到[0, n]范围内）。
2. 每次计算并更新该区间范围内每个点j的furthest[j]。
3. 最后从土地 0 开始，一路遍历到土地 n，用与跳跃游戏相同的end/last双变量法记录水龙头数目。

可以发现，它与上一题的差异只在于输入数据的表达方式（水龙头中心点 + 半径 vs. 片段左右端点），核心的“预处理出最右覆盖 + 触界计数”骨架完全相同。

代码

代码支持：Python3

class Solution: def minTaps(self, n: int, ranges: List[int]) -> int: # furthest[j] 表示：能覆盖点 j 的水龙头中，覆盖到的最右位置 furthest, ans, cur = [0] * n, 0, 0 # 预处理：把每个水龙头的灌溉半径转化为最右覆盖信息 for i in range(n + 1): for j in range(max(0, i - ranges[i]), min(n, i + ranges[i])): furthest[j] = max(furthest[j], min(n, i + ranges[i])) # 老套路：触界计数 end = last = 0 for i in range(n): # 点 i 没有任何水龙头能覆盖到，直接判失败 if furthest[i] == 0: return -1 last = max(last, furthest[i]) if i == end: end = last ans += 1 return ans

代码细节说明：预处理内层循环的边界max(0, i - ranges[i])与min(n, i + ranges[i])用于把灌溉区间裁剪到花园范围[0, n]内；主循环中furthest[i] == 0表示点i无任何水龙头覆盖，属于题目要求返回-1的失败情形。原题代码中的cur变量并未参与逻辑运算，仅作占位，不影响正确性。

复杂度分析

• 时间复杂度：$O(\sum_{i=1}^{n}R[i] + n)$，其中R[i]为ranges[i]对应的灌溉区间长度。
• 空间复杂度：$O(n)$，用于furthest数组。

三题对照：同一套骨架的三副面孔

将三道题并排对比，可以清晰看到它们共享同一个代码骨架：

三题的公共模板可以概括为：

# 预处理阶段：把题目数据改写成 furthest 数组（表示"覆盖到 i 时能到的最右端"） # 主循环阶段： end = last = ans = 0 for i in range(范围): last = max(last, furthest[i]) if 出现断裂（无法向前推进）: return -1 if i == end: # 到达本次覆盖边界 ans += 1 end = last # 开启下一段覆盖 return ans

只要抓住“维护最右可达边界、触界即计数、断裂即返回 -1”这三点，覆盖类问题无论包装成跳跃、视频还是水龙头，都能快速套用。

总结

对于极值问题，我们可以考虑使用动态规划和贪心两种思路；覆盖类问题两种方法同样适用，只不过贪心的代码与复杂度通常更简单。但相应地，贪心的难点在于如何证明局部最优解就能得到全局最优解——这也是每道贪心题必须想清楚的问题：为什么“每次选覆盖最远的小区间”就能保证总区间数最少？答案正蕴含在覆盖问题的结构里：新区间要接上前一区间的右端点，其唯一价值在于把可达右边界推得更远，因此每步贪心地取最远者，步数一定不会多于任何其他合法方案。

通过这三道题的学习，希望你能够明白覆盖类问题的套路——其底层都是一样的。明白了这些，再回头去看覆盖类的其他题目，你可能会发现一个新的世界：它们都只是同一套“维护最右边界 + 触界计数”思想的不同包装而已。

延伸阅读

• 本文主题的官方讲解见 thinkings/greedy.en.md（中文版 thinkings/greedy.md）；
• 跳跃游戏 II 的初级版“能否到达终点”见 problems/55.jump-game.md，其前置知识一节同样指向贪心专题；
• 极值问题的另一解法视角可参考 thinkings/dynamic-programming.en.md，覆盖类问题用 DP 亦可解，只是复杂度通常更高。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode