1326. 灌溉花园的最少水龙头数目
题目描述
x 轴上有一个一维花园，占据区间 [0, n]。在点 0, 1, ..., n 上各有一个水龙头，共 n + 1 个。
输入整数 n 和长度为 n + 1 的数组 ranges，下标从 0 开始。打开点 i 的水龙头后，能浇到区间 [i - ranges[i], i + ranges[i]]。
返回让整个 [0, n] 都被浇到最少需要打开几个水龙头。如果全部打开仍有地方浇不到，返回 -1。
示例 1
输入：n = 5, ranges = [3,4,1,1,0,0] 输出：1
解释：点 1 的水龙头能覆盖 [-3,5]，单独打开它就够了。
示例 2
输入：n = 3, ranges = [0,0,0,0] 输出：-1
解释：每个水龙头只能浇到自己所在的点，点与点之间的区域浇不到。
数据范围
1 <= n <= 10^4ranges.length == n + 10 <= ranges[i] <= 100
解题思路：预处理最远覆盖 + 贪心（类似跳跃游戏）
先把每个水龙头化成区间，记 far[l] 为从左端点 l 出发能覆盖到的最远位置。之后的问题就是“跳跃游戏 II”：从 0 出发，在当前已覆盖的范围 end 内不断更新最远可达 reach；走到 end 时必须再开一个水龙头，把 end 推到 reach。若此时 reach 没有超过 i，说明 i 之后的一段无法覆盖，返回 -1。这是对“前缀最少区间数”的贪心优化：每次都选能伸得最远的区间不会更差。
为什么正确
扫描到 i 时，ans 个水龙头已覆盖 [0, end]，reach 是左端点不超过 i 的所有区间中能到达的最远位置。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
判断无解要用 reach <= i（等于也不行，说明区间 [i, i+1] 没人覆盖），而且只在 i == end 时判断。另外循环只到 n - 1，走到 n 时已经覆盖完毕。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
far = [0] * (n + 1)
for i, r in enumerate(ranges):
l = max(0, i - r)
far[l] = max(far[l], i + r)
ans = end = reach = 0
for i in range(n):
reach = max(reach, far[i])
if i == end:
if reach <= i:
return -1
ans += 1
end = reach
return ansclass Solution {
public int minTaps(int n, int[] ranges) {
int[] far = new int[n + 1];
for (int i = 0; i <= n; i++) {
int r = ranges[i];
int l = Math.max(0, i - r);
far[l] = Math.max(far[l], i + r);
}
int ans = 0, end = 0, reach = 0;
for (int i = 0; i < n; i++) {
reach = Math.max(reach, far[i]);
if (i == end) {
if (reach <= i) {
return -1;
}
ans++;
end = reach;
}
}
return ans;
}
}class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> far(n + 1, 0);
for (int i = 0; i <= n; i++) {
int r = ranges[i];
int l = max(0, i - r);
far[l] = max(far[l], i + r);
}
int ans = 0, end = 0, reach = 0;
for (int i = 0; i < n; i++) {
reach = max(reach, far[i]);
if (i == end) {
if (reach <= i) {
return -1;
}
ans++;
end = reach;
}
}
return ans;
}
};func minTaps(n int, ranges []int) int {
far := make([]int, n+1)
for i, r := range ranges {
l := max(0, i-r)
far[l] = max(far[l], i+r)
}
ans, end, reach := 0, 0, 0
for i := 0; i < n; i++ {
reach = max(reach, far[i])
if i == end {
if reach <= i {
return -1
}
ans++
end = reach
}
}
return ans
}var minTaps = function(n, ranges) {
const far = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
const r = ranges[i];
const l = Math.max(0, i - r);
far[l] = Math.max(far[l], i + r);
}
let ans = 0, end = 0, reach = 0;
for (let i = 0; i < n; i++) {
reach = Math.max(reach, far[i]);
if (i === end) {
if (reach <= i) {
return -1;
}
ans++;
end = reach;
}
}
return ans;
};function minTaps(n: number, ranges: number[]): number {
const far: number[] = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
const r = ranges[i];
const l = Math.max(0, i - r);
far[l] = Math.max(far[l], i + r);
}
let ans = 0, end = 0, reach = 0;
for (let i = 0; i < n; i++) {
reach = Math.max(reach, far[i]);
if (i === end) {
if (reach <= i) {
return -1;
}
ans++;
end = reach;
}
}
return ans;
}其他解法
动态规划对每个位置算出精确的最少数量，正确性一目了然；贪心每次在当前覆盖范围内选能延伸最远的区间，把复杂度降到线性，但需要“选最远的不会更差”这一论证。
解法 2：动态规划 时间 O(n · R)，R 为最大浇灌半径，空间 O(n)
先求出 far[l]：所有左端点为 l 的水龙头里，最远能覆盖到的位置。设 dp[j] 为覆盖区间 [0, j] 所需的最少水龙头数，dp[0] = 0。从左到右枚举左端点 l，如果 dp[l] 可达，那么在 l 处打开一个从 l 覆盖到 far[l] 的水龙头，就能把 (l, far[l]] 内每个位置的答案更新为 dp[l] + 1。由于左端点按顺序处理，用到 dp[l] 时它已经是最终值。最后 dp[n] 就是答案，不可达时返回 -1。
状态和转移含义明确，不需要证明贪心选择的正确性，也容易改造成带权（每个水龙头代价不同）的版本。时间复杂度多了一个与半径相关的因子。
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
far = [0] * (n + 1)
for i, r in enumerate(ranges):
l = max(0, i - r)
far[l] = max(far[l], min(n, i + r))
INF = n + 2
dp = [INF] * (n + 1)
dp[0] = 0
for l in range(n + 1):
if dp[l] == INF:
continue
for j in range(l + 1, far[l] + 1):
dp[j] = min(dp[j], dp[l] + 1)
return -1 if dp[n] == INF else dp[n]class Solution {
public int minTaps(int n, int[] ranges) {
int[] far = new int[n + 1];
for (int i = 0; i <= n; i++) {
int l = Math.max(0, i - ranges[i]);
far[l] = Math.max(far[l], Math.min(n, i + ranges[i]));
}
final int INF = n + 2;
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int l = 0; l <= n; l++) {
if (dp[l] == INF) continue;
for (int j = l + 1; j <= far[l]; j++) dp[j] = Math.min(dp[j], dp[l] + 1);
}
return dp[n] == INF ? -1 : dp[n];
}
}class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> far(n + 1, 0);
for (int i = 0; i <= n; i++) {
int l = max(0, i - ranges[i]);
far[l] = max(far[l], min(n, i + ranges[i]));
}
const int INF = n + 2;
vector<int> dp(n + 1, INF);
dp[0] = 0;
for (int l = 0; l <= n; l++) {
if (dp[l] == INF) continue;
for (int j = l + 1; j <= far[l]; j++) dp[j] = min(dp[j], dp[l] + 1);
}
return dp[n] == INF ? -1 : dp[n];
}
};func minTaps(n int, ranges []int) int {
far := make([]int, n+1)
for i, r := range ranges {
l := max(0, i-r)
far[l] = max(far[l], min(n, i+r))
}
INF := n + 2
dp := make([]int, n+1)
for i := range dp {
dp[i] = INF
}
dp[0] = 0
for l := 0; l <= n; l++ {
if dp[l] == INF {
continue
}
for j := l + 1; j <= far[l]; j++ {
dp[j] = min(dp[j], dp[l]+1)
}
}
if dp[n] == INF {
return -1
}
return dp[n]
}var minTaps = function(n, ranges) {
const far = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
const l = Math.max(0, i - ranges[i]);
far[l] = Math.max(far[l], Math.min(n, i + ranges[i]));
}
const INF = n + 2;
const dp = new Array(n + 1).fill(INF);
dp[0] = 0;
for (let l = 0; l <= n; l++) {
if (dp[l] === INF) continue;
for (let j = l + 1; j <= far[l]; j++) dp[j] = Math.min(dp[j], dp[l] + 1);
}
return dp[n] === INF ? -1 : dp[n];
};function minTaps(n: number, ranges: number[]): number {
const far: number[] = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
const l = Math.max(0, i - ranges[i]);
far[l] = Math.max(far[l], Math.min(n, i + ranges[i]));
}
const INF = n + 2;
const dp: number[] = new Array(n + 1).fill(INF);
dp[0] = 0;
for (let l = 0; l <= n; l++) {
if (dp[l] === INF) continue;
for (let j = l + 1; j <= far[l]; j++) dp[j] = Math.min(dp[j], dp[l] + 1);
}
return dp[n] === INF ? -1 : dp[n];
}