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]问最少选择多少个小区间使得这些小区间的并集可以覆盖整个大区间。我们挑选三道题来讲解跳跃游戏 II困难视频拼接中等灌溉花园的最少水龙头数目困难下面逐一拆解。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。代码代码支持Python3class 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。代码代码支持Python3class 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_{i1}^{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 题完全一致仍然采用贪心策略尽量找到能够覆盖最远最右位置的水龙头并记录它最右覆盖到的土地。算法分三步使用furthest[i]记录经过预处理后、能够覆盖点i的所有水龙头中最靠右的覆盖位置。一共有n 1个水龙头逐个遍历每个水龙头覆盖区间为[i - ranges[i], i ranges[i]]需裁剪到[0, n]范围内。每次计算并更新该区间范围内每个点j的furthest[j]。最后从土地 0 开始一路遍历到土地 n用与跳跃游戏相同的end/last双变量法记录水龙头数目。可以发现它与上一题的差异只在于输入数据的表达方式水龙头中心点 半径 vs. 片段左右端点核心的“预处理出最右覆盖 触界计数”骨架完全相同。代码代码支持Python3class 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_{i1}^{n}R[i] n)$其中R[i]为ranges[i]对应的灌溉区间长度。空间复杂度$O(n)$用于furthest数组。三题对照同一套骨架的三副面孔将三道题并排对比可以清晰看到它们共享同一个代码骨架维度45. 跳跃游戏 II1024. 视频拼接1326. 灌溉水龙头输入形式一维数组每个位置的最大跳跃长度二维区间数组片段起止点中心点 半径数组覆盖对象数组下标 [0, n-1]时间轴 [0, T]花园线段 [0, n]预处理无需数组本身即跳跃能力桶思想furthest[i]记录覆盖到点 i 时能到的最右端半径展开furthest[j]记录覆盖点 j 的最右位置主循环furthest max(furthest, nums[i] i)last max(last, furthest[i])last max(last, furthest[i])触界更新if i end: cnt 1; end furthestif end i: ans 1; end lastif i end: end last; ans 1失败判断题目保证可达无需判断last i返回 -1furthest[i] 0返回 -1三题的公共模板可以概括为# 预处理阶段把题目数据改写成 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考