贪婪策略是一种常见的算法思想。具体是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑。他所做出的是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，比如硬币找零问题，关键是贪心策略的选择。
选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关，这点和动态规划一样。贪婪策略和动态规划类似，大多数情况也都是用来处理极值问题。
LeetCode 上对于贪婪策略有 73 道题目。我们将其分成几个类型来讲解，截止目前我们暂时只提供覆盖问题，其他类型可以期待我的新书或者之后的题解文章。
我们挑选三道来讲解，这三道题除了使用贪婪法，你也可以尝试动态规划来解决。
- 45. 跳跃游戏 II，困难
- 1024. 视频拼接，中等
- 1326. 灌溉花园的最少水龙头数目，困难
覆盖问题的一大特征，我们可以将其抽象为给定数轴上的一个大区间 I 和 n 个小区间 i[0], i[1], ..., i[n - 1]，问最少选择多少个小区间，使得这些小区间的并集可以覆盖整个大区间。
我们来看下这三道题吧。
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
这里我们使用贪婪策略来解。即每次都在可跳范围内选择可以跳地更远的位置。
如下图，开始的位置是 2，可跳的范围是橙色节点的。由于 3 可以跳的更远，足以覆盖 2 的情况，因此应该跳到 3 的位置。
当我们跳到 3 的位置后。 如下图，能跳的范围是橙色的 1，1，4。由于 4 可以跳的更远，因此跳到 4 的位置。
写代码的话，我们可以使用 end 表示当前能跳的边界，对应第一个图的橙色 1，第二个图的橙色 4。并且遍历数组的时候，到了边界，就重新更新边界。
代码支持：Python3
Python3 Code:
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)$。
你将会获得一系列视频片段，这些片段来自于一项持续时长为 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:
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)$。
在 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:
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 多页的电子书已经开发下载了，大家可以去我的公众号《力扣加加》后台回复电子书获取。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
