# 贪婪策略

贪婪策略是一种常见的算法思想。具体是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑。他所做出的是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，比如硬币找零问题，关键是贪心策略的选择。

选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关，这点和动态规划一样。贪婪策略和动态规划类似，大多数情况也都是用来处理`极值问题`。

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 可以跳的更远，足以覆盖 2 的情况，因此应该跳到 3 的位置。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghluifqw9sj309i03xq2t.jpg)

当我们跳到 3 的位置后。 如下图，能跳的范围是橙色的 1，1，4。由于 4 可以跳的更远，因此跳到 4 的位置。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghluimff8dj30c1039wed.jpg)

写代码的话，我们可以使用 end 表示当前能跳的边界，对应第一个图的橙色 1，第二个图的橙色 4。并且遍历数组的时候，到了边界，就重新更新边界。

> 图来自 https://leetcode-cn.com/u/windliang/

#### 代码

代码支持：Python3

Python3 Code:

```python
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)$。

### 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], ...]`

> 注意并不需要真正地排序，而是类似桶排序的思路，使用额外的空间，具体参考代码区

这是不是就相当于上面跳跃游戏中的：[4,0,2]。 至此我们成功将这道题转换为了上面已经做出来的题。 只不过有一点不同，那就是上面的题保证可以跳到最后，而这道题是可能拼不出来的，因此这个临界值需要注意，具体参考后面的代码区。

#### 代码

代码支持：Python3

Python3 Code:

```python

class 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_{i=1}^{n}ranges[i] + T)$，其中 ranges[i] 为 clips[i] 的区间长度。

- 空间复杂度：$O(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：
```

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghluiubf2gj30bm05xmx4.jpg)

```
输入：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:

```python

class 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_{i=1}^{n}R[i] + n)$，其中 R[i] 为 ranges[i] 的区间长度。

- 空间复杂度：$O(n)$。

## 总结

极值问题我们可以考虑使用动态规划和贪心，而覆盖类的问题使用动态规划和贪心都是可以的，只不过使用贪心的代码和复杂度通常都会更简单。但是相应地，贪心的难点在于如何证明局部最优解就可以得到全局最优解。通过这几道题的学习，希望你能够明白覆盖类问题的套路，其底层都是一样的。明白了这些， 你回头再去看覆盖类的题目，或许会发现新的世界。

我整理的 1000 多页的电子书已经开发下载了，大家可以去我的公众号《力扣加加》后台回复电子书获取。

![](https://cdn.jsdelivr.net/gh/azl397985856/cdn/2020-10-17/1602928846461-image.png)

![](https://cdn.jsdelivr.net/gh/azl397985856/cdn/2020-10-17/1602928862442-image.png)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)