文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载贪婪策略贪心算法是算法面试中最常被考察的思维范式之一。本文基于 leetcode 题解仓库中的贪婪策略专题系统讲解贪心的适用前提与无后效性这一核心约束并以 45. 跳跃游戏 II、1024. 视频拼接、1326. 灌溉花园的最少水龙头数目三道覆盖类问题为主线演示如何把选择最远能覆盖的位置这一套贪心模板反复套用。读完本文你将掌握覆盖类问题的统一抽象与代码骨架并能区分贪心与动态规划的适用场景。什么是贪婪策略贪婪策略是一种常见的算法思想在对问题求解时总是做出在当前看来是最好的选择而不从整体最优的角度加以考虑。也就是说贪心算法做出的是某种意义上的局部最优解。但必须清醒认识到贪心算法并不是对所有问题都能得到整体最优解硬币找零问题就是一个反例。关键在于贪心策略的选择——只有选对了策略局部最优才能自然累积成全局最优。使用贪心的两个重要前提最优子结构问题的最优解包含子问题的最优解因此可以走一步看一步地递推无后效性无后向性某个状态以前的过程不会影响以后的状态决策只与当前状态有关。这一点和动态规划完全一致也是判断能否使用贪心的核心标尺。在原仓库的动态规划专题中作者给出了一个非常形象的对比动态规划会把所有可能的转移全部模拟一遍最后挑选一个最优解而如果你没有模拟所有可能直接走了一条最优解那就是贪心算法了。两者处理的大多数情况都是极值问题区别在于贪心放弃了枚举全部状态的保险换来了更低的复杂度和更简洁的代码代价是需要证明局部最优能推出全局最优——这恰恰是贪心最难的环节。覆盖问题的统一抽象LeetCode 上贪婪策略类题目数量可观原专题统计约有 70 道具体数字以写作时点的题目集为准可分为多个子类型。本专题聚焦其中最典型的覆盖问题其数学抽象可以统一描述为给定数轴上的一个大区间I和n个小区间i[0], i[1], ..., i[n-1]问最少选择多少个小区间使得这些小区间的并集可以覆盖整个大区间。覆盖问题的一个突出特征是并集覆盖决定了选区的顺序无关性——只要最终并集盖满大区间即可先选哪个区间并不影响结果这正满足了贪心的无后效性要求。下面用三道题逐步展开它们除了用贪心也都可以尝试用动态规划解决是理解两种思想差异的绝佳素材跳跃游戏 II困难视频拼接中等灌溉花园的最少水龙头数目困难说明以上三题在 LeetCode 原站为 45 / 1024 / 1326。当前仓库的 problems 目录中收录了同系列的 55. 跳跃游戏跳跃游戏 II 的判定版前身可对照阅读。45. 跳跃游戏 II最朴素的贪心最远题目描述给定一个非负整数数组你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。思路使用贪婪策略每次都在可跳范围内选择可以跳得更远的位置。起始位置是 2可跳范围为下标 1、2橙色节点。由于下标 1 处数值 3 可以跳得更远足以覆盖下标 2 处数值 2 的情况因此第一步应该跳到位置 1值 3。跳到位置 1 后可跳范围是下标 2、3、4值 1、1、4。由于 4 可以跳得更远因此下一步跳到位置 4到达终点总跳跃次数为 2。写代码时用两个变量维护信息end表示当前这一跳能够到达的边界第一跳的边界是下标 2第二跳的边界是下标 4furthest表示遍历过程中能到达的最远位置每次迭代用max(furthest, nums[i] i)更新。遍历数组时一旦i到达end即本跳边界耗尽就必须再跳一次cnt 1并把end更新为furthest进入下一跳。注意循环只需遍历到n - 2因为最后一个位置无需再跳。代码代码支持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. 跳跃游戏 I 的关系跳跃游戏 II 是仓库中55. 跳跃游戏的升级版55 题只要求判断能否到达最后一个位置II 要求输出最少跳跃次数。两者的贪心内核完全一致——都是用一个变量记录当前能到达的最大索引并持续更新区别在于 55 题只做可达性判定而 II 在遍历到end时额外累加跳跃次数。55 题在仓库中提供了 Javascript、C、Java、Python3 四种语言的实现其核心循环如下Javascript 版本var canJump function (nums) { let max 0; // 能够走到的数组下标 for (let i 0; i nums.length; i) { if (max i) return false; // 当前这一步都走不到后面更走不到了 max Math.max(nums[i] i, max); } return max nums.length - 1; };将这两题对照学习效果最佳先理解 55 题的max单调更新再理解 II 的end/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两个变量不断贪心更新。不同的是本题的输入是一个二维数组若干区间需要先做一层预处理。以题目给出的数据为例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 开始的片段中能覆盖到最远的是 [0,4]覆盖到 4从 1 开始的片段中最远是 [1,4]从 2 开始的片段中最远是 [2,6]。提取每个起始点的最远右端点恰好构成[4,4,6,...]这样的数组——这不就等价于上一题跳跃游戏中的[4,0,2]吗至此我们成功把二维区间问题转换为一维的跳跃游戏问题。需要特别指出两点不需要真正排序可以用类似桶排序的思路直接用下标做映射用额外空间换时间具体见代码区多了一个临界值判断上一题保证总是可以到达最后而本题可能拼不完整条视频例如示例 2 返回 -1因此遍历中一旦出现当前位置无法被任何片段延伸到的情况last i必须提前返回 -1。代码代码支持Python3class Solution: def videoStitching(self, clips: List[List[int]], T: int) - int: furthest [0] * (T) for s, e in clips: for i in range(s, e 1): # 无需考虑这也是我可以建立一个大小为 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]的区间长度。空间复杂度$O(T)$furthest数组长度为T。1326. 灌溉花园的最少水龙头数目同一模板的第三次复现题目描述在 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思路思路与上面两题完全一致仍然采用贪心策略尽量找到能够覆盖最远最右位置的水龙头并记录它最右覆盖的土地。具体算法分两步预处理使用furthest[i]记录经过每一个位置 i 能够覆盖到的最右侧土地。共有n 1个水龙头遍历n 1次对每个水龙头更新其左右边界[i - ranges[i], i ranges[i]]内所有位置的furthest值注意用max(0, ...)和min(n, ...)把区间裁剪到花园范围内。扫描从土地 0 一直遍历到土地n - 1用end/last双变量累计打开的水龙头数目——这一步和跳跃游戏 II 的扫描循环几乎一模一样。对比可以发现本题的预处理把每个水龙头的覆盖区间转换为furthest数组后后续扫描与 45 题、1024 题共享同一套模板只是临界值判断略有不同本题用furthest[i] 0判断位置 i 没有任何水龙头能覆盖直接返回 -1。代码代码支持Python3class Solution: def minTaps(self, n: int, ranges: List[int]) - int: 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): if furthest[i] 0: return -1 last max(last, furthest[i]) if i end: end last ans 1 return ans复杂度分析时间复杂度$O(\sum_{i1}^{n} R[i] n)$其中R[i]为ranges[i]的区间长度。空间复杂度$O(n)$furthest数组长度为n。覆盖问题家族与贪心的其他类型这三道题构成了覆盖类问题的贪心三连底层套路完全一致预处理把原始输入跳跃数组 / 视频区间 / 水龙头半径转换成从每个位置能到达的最远位置数组furthest贪心扫描end记录当前段边界last记录当前段内能延伸到的最远点走到end就段数 1 并推进end last临界处理一旦出现无法延伸last i或furthest[i] 0返回 -1 表示无法覆盖。这个模板在仓库的题解集中还有多个变体可以对照训练55. 跳跃游戏仅判可达性的最简版先写熟它再写 II455. 分发饼干排序 双指针的经典贪心体现先排序再贪心的常见搭配330. 按要求补齐数组贪心 维护覆盖端点[1, x]当数组当前数字无法延伸覆盖区间时补充数字x 1将区间扩张到[1, 2*x1]与覆盖问题扩张最远端点的思想一脉相承。总结极值问题可以优先考虑动态规划和贪心两种思路覆盖类问题两者也都适用但贪心的代码与复杂度通常更简单动态规划需要完整的状态定义、转移方程与边界初始化而贪心往往只需要一两个变量加一次线性扫描。相应地贪心的难点在于证明局部最优解可以累积得到全局最优解——覆盖类问题之所以能放心贪心正是因为每次都选延伸最远的区间不会让后续选择变差满足无后效性。建议按如下顺序消化本专题先做 55. 跳跃游戏熟悉最远可达位置的单调更新再做 45 题掌握end/furthest双变量的跳段计数最后用 1024 和 1326 验证预处理 同一扫描模板的迁移能力。当你发现这三道题本质上是同一道题的不同马甲覆盖类问题的新的世界就打开了。本专题收录于仓库算法专题索引与动态规划专题、回溯专题等共同构成完整的算法套路学习路径更多贪心题目可查阅仓库 problems 目录下的单题题解。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 1288 Remove Covered Intervals区间覆盖判定与两种排序贪心策略详解LeetCode 1288 Remove Covered Intervals区间覆盖判定与两种排序贪心策略详解 本篇围绕 LeetCode 1288「移除被覆示例工程教程gh_mirrors/leet/leetcode项目贪心选择性质题解分析gh_mirrors/leet/leetcode项目贪心选择性质题解分析 贪心算法概述 贪心算法Greedy Algorithm是一种在每一步选择中都采取教程文档LeetCode 122 买卖股票的最佳时机 II贪心累加所有上升区间的最优策略leetcode 题解仓库详解LeetCode 122 买卖股票的最佳时机 II贪心累加所有上升区间的最优策略leetcode 题解仓库详解 本文基于 leetcode 题解仓库中 1文档教程知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考