# 《贪婪策略》专题 # 贪婪策略 贪婪策略是一种常见的算法思想，具体是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关，这点和动态规划一样。贪婪策略和动态规划类似，大多数情况也都是用来处理`极值问题`。 LeetCode 上对于贪婪策略有 73 道题目。我们将其分成几个类型来讲解，截止目前我们暂时只提供`覆盖`问题，其他的可以期待我的新书或者之后的题解文章。 ## 覆盖 我们挑选三道来讲解，这三道题除了使用贪婪法，你也可以尝试动态规划来解决。 - [45. 跳跃游戏 II](https://leetcode-cn.com/problems/jump-game-ii/)，困难 - [1024. 视频拼接](https://leetcode-cn.com/problems/video-stitching/)，中等 - [1326. 灌溉花园的最少水龙头数目](https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/)，困难 覆盖问题的一大特征，我们可以将其抽象为`给定数轴上的一个大区间 I 和 n 个小区间 i[0], i[1], ..., i[n - 1]，问最少选择多少个小区间，使得这些小区间的并集可以覆盖整个大区间。` 我们来看下这三道题吧。 ### 45. 跳跃游戏 II #### 题目描述 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: \[2,3,1,1,4\] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 #### 思路 贪婪策略，即我们每次在可跳范围内选择可以使得跳的更远的位置，由于题目保证了`你总是可以到达数组的最后一个位置`,因此这种算法是完备的。 如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。  如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置。  写代码的话，我们用 end 表示当前能跳的边界，对于上边第一个图的橙色 1，第二个图中就是橙色的 4，遍历数组的时候，到了边界，我们就重新更新新的边界。 > 图来自 <https://leetcode-cn.com/u/windliang/> #### 代码 代码支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">jump</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n, cnt, furthest, end = len(nums), <span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">1</span>): furthest = max(furthest, nums[i] + i) <span class="hljs-keyword">if</span> i == end: cnt += <span class="hljs-params">1</span> end = furthest <span class="hljs-keyword">return</span> cnt ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N)。 - 空间复杂度：O(1)O(1)O(1)。 ### 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 #### 思路 贪婪策略，我们选择满足条件的最大值。和上面的不同，这次我们需要手动进行一次排序，实际上贪婪策略经常伴随着排序，我们按照 clip\[0\]从小到大进行排序。  如图： - 1 不可以，因此存在断层 - 2 可以 - 3 不行，因为不到 T 我们当前的 clip 开始结束时间分别为 s，e。 上一段 clip 的结束时间是 t1，上上一段 clip 结束时间是 t2。 那么这种情况下 t1 实际上是不需要的，因为 t2 完全可以覆盖它：  那什么样 t1 才是需要的呢？如图：  用代码来说的话就是`s > t2 and t2 <= t1` #### 代码 代码支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">videoStitching</span><span class="hljs-params">(self, clips: List[List[int]], T: int)</span> -> int:</span> <span class="hljs-title"># t1 表示选取的上一个clip的结束时间</span> <span class="hljs-title"># t2 表示选取的上上一个clip的结束时间</span> t2, t1, cnt = <span class="hljs-params">-1</span>, <span class="hljs-params">0</span>, <span class="hljs-params">0</span> clips.sort(key=<span class="hljs-keyword">lambda</span> a: a[<span class="hljs-params">0</span>]) <span class="hljs-keyword">for</span> s, e <span class="hljs-keyword">in</span> clips: <span class="hljs-title"># s > t1 已经确定不可以了， t1 >= T 已经可以了</span> <span class="hljs-keyword">if</span> s > t1 <span class="hljs-keyword">or</span> t1 >= T: <span class="hljs-keyword">break</span> <span class="hljs-keyword">if</span> s > t2 <span class="hljs-keyword">and</span> t2 <= t1: cnt += <span class="hljs-params">1</span> t2 = t1 t1 = max(t1,e) <span class="hljs-keyword">return</span> cnt <span class="hljs-keyword">if</span> t1 >= T <span class="hljs-keyword">else</span> - <span class="hljs-params">1</span> ``` ``` **复杂度分析** - 时间复杂度：由于使用了排序（假设是基于比较的排序），因此时间复杂度为 O(NlogN)O(NlogN)O(NlogN)。 - 空间复杂度：O(1)O(1)O(1)。 ### 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 - 最后从土地 0 开始，一直到土地 n ，记录水龙头数目 #### 代码 代码支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minTaps</span><span class="hljs-params">(self, n: int, ranges: List[int])</span> -> int:</span> furthest, cnt, cur = [<span class="hljs-params">0</span>] * n, <span class="hljs-params">0</span>, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">1</span>): l = max(<span class="hljs-params">0</span>, i - ranges[i]) r = min(n, i + ranges[i]) <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(l, r): furthest[j] = max(furthest[j], r) <span class="hljs-keyword">while</span> cur < n: <span class="hljs-keyword">if</span> furthest[cur] == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span> cur = furthest[cur] cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> cnt ``` ``` **复杂度分析** - 时间复杂度：时间复杂度取决 l 和 r，也就是说取决于 ranges 数组的值，假设 ranges 的平均大小为 Size 的话，那么时间复杂度为 O(N∗Size)O(N \* Size)O(N∗Size)。 - 空间复杂度：我们使用了 furthest 数组， 因此空间复杂度为 O(N)O(N)O(N)。