题目描述
leetcode 困难题
在 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：
1
2
3
4
5
6
7
8
9
10
| 输入：n = 5, ranges =
输出：1
解释：
点 0 处的水龙头可以灌溉区间
点 1 处的水龙头可以灌溉区间
点 2 处的水龙头可以灌溉区间
点 3 处的水龙头可以灌溉区间
点 4 处的水龙头可以灌溉区间
点 5 处的水龙头可以灌溉区间
只需要打开点 1 处的水龙头即可灌溉整个花园 。
|
示例2：
1
2
3
| 输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。
|
提示1：
1
2
3
| 1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100
|
贪心
为了使水龙头数目最少，我们可以先贪心的选择范围最大的水龙头。
但存在一种情况，如果存在某个范围只有某个水龙头能够灌溉到，那么虽然该水龙头范围可能不是最大的，但是为了满足灌溉整个花园的条件，必须选择该水龙头，这种情况下某个范围更大的水龙头反而不是必选的。
由于存在上面的情况，所以需要额外加上一个限制，设所选择的上一个水龙头覆盖的右边界为 $rightMax$ ，那么我们选择的下一个水龙头的左边界必须至少小于 $rightMax$ ，在满足该条件的前提下，再选择右边界尽量大的水龙头，并取其右边界作为新的 $rightMax$ 即可。
为了方便判断下一个水龙头能否覆盖到 $rightMax$ ，我们可以使用最小堆，排序条件为左边界，并在该过程中维护下一个 $rightMax$ 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int minTaps(int n, int[] ranges) {
List<int[]> tapList = new ArrayList<>();
for(int i = 0; i < ranges.length; i++){
if (ranges[i] == 0) {
continue;
}
tapList.add(new int[]{i, ranges[i]});
}
tapList.sort(Comparator.comparingInt(a -> (a[0] - a[1])));
int ans = 0;
int rightMax = 0, nextRightMax = 0;
for(int[] tap : tapList){
if (tap[0] - tap[1] > rightMax) {
rightMax = nextRightMax;
ans++;
if (rightMax >= n) {
return ans;
}
}
if (tap[0] - tap[1] > rightMax) {
return -1;
}
nextRightMax = Math.max(nextRightMax, tap[0] + tap[1]);
}
return nextRightMax >= n ? ans + 1 : -1;
}
}
|
动态规划
设 $dp[i]$ 表示满足花园 $0$ 到 $i$ 点被灌溉的最少水龙头数，那么 $dp[n]$ 为答案。
对于某个水龙头 ，灌溉范围为 $[left, right]$ ，假设 $dp[:left]$ 已经求出，那么对于 $dp[left]…dp[right]$，就有以下转移方程
$$
\begin{align}
&dp(i) = min(dp[i], dp[left] + 1) left <= i <= right \\
\end{align}
$$
也就是说我们需要保证在计算到 $dp[i]$ 时，其对应的 $dp[left]$ 已经计算完毕，这点我们可以通过对水龙头覆盖的左区间进行排序来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int minTaps(int n, int[] ranges) {
List<int[]> tapList = new ArrayList<>();
for(int i = 0; i < ranges.length; i++){
if (ranges[i] == 0) {
continue;
}
tapList.add(new int[]{i, ranges[i]});
}
tapList.sort(Comparator.comparingInt(a -> (a[0] - a[1])));
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int[] tap : tapList){
int left = Math.max(0, tap[0] - tap[1]);
int right = Math.min(n, tap[0] + tap[1]);
if(dp[left] == Integer.MAX_VALUE){
return -1;
}
for(int i = left; i <= right; i++){
dp[i] = Math.min(dp[i], dp[left] + 1);
}
}
return dp[n] != Integer.MAX_VALUE ? dp[n] : -1;
}
}
|