灌溉花园的最少水龙头数如何转化为区间覆盖？

简化版

灌溉花园可以把每个水龙头 i 转成覆盖区间 [i-ranges[i], i+ranges[i]]，问题就变成用最少区间覆盖 [0,n]。贪心做法和跳跃游戏类似：在当前覆盖范围内，选择能把右边界延伸最远的水龙头。

详细版

先构造 maxReach[left]，表示从某个左端点开始最多能覆盖到哪里。对每个水龙头计算 left=max(0,i-range)、right=min(n,i+range)，更新 maxReach[left]。然后从 0 扫到 n，维护当前已选择水龙头能覆盖到的 curEnd 和当前扫描范围内下一步最远的 nextEnd。

当扫描位置到达 curEnd 时，必须开启一个新水龙头，把覆盖推进到 nextEnd。如果 nextEnd <= i，说明断档，返回 -1。时间复杂度 O(n)。

完整版教学

一、为什么水龙头能转成区间

第 i 个水龙头覆盖范围是：

[i - ranges[i], i + ranges[i]]

花园范围只有 [0,n]，所以要截断到边界：

left = max(0, i - ranges[i])
right = min(n, i + ranges[i])

转完后，题目就不再像“水龙头问题”，而是标准区间覆盖。

二、目标为什么是覆盖 [0,n]

花园从位置 0 到位置 n，每个点都要被至少一个开启的水龙头覆盖。选择水龙头越少越好。

目标线段：0 -------- n
水龙头：   [----]
另一个：       [------]

如果中间有任何断档，就无法灌溉整个花园。

三、为什么可以用跳跃游戏式贪心

对每个可能左端点，记录它能到达的最远右端。扫描位置 i 时，持续更新当前范围内能到达的最远位置 nextEnd。当走到当前覆盖边界 curEnd，必须选择一个水龙头把边界推到 nextEnd。

变量	含义
`curEnd`	已经用当前数量水龙头保证覆盖到的位置
`nextEnd`	再开一个水龙头最多能扩展到的位置

记忆钩子：最少区间覆盖和跳跃游戏 II 是同一类“分层推进右边界”。

四、断档怎么判断

如果当前位置 i 已经到达当前覆盖边界，但 nextEnd <= i，说明没有任何可用水龙头能覆盖并跨过这个点。

curEnd = 3
i = 3
nextEnd = 3

覆盖无法继续向右推进，直接返回 -1。

五、代码模板

int minTaps(int n, int[] ranges) {
    int[] maxReach = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int left = Math.max(0, i - ranges[i]);
        int right = Math.min(n, i + ranges[i]);
        maxReach[left] = Math.max(maxReach[left], right);
    }
    int ans = 0, curEnd = 0, nextEnd = 0;
    for (int i = 0; i < n; i++) {
        nextEnd = Math.max(nextEnd, maxReach[i]);
        if (i == curEnd) {
            if (nextEnd <= i) return -1;
            ans++;
            curEnd = nextEnd;
        }
    }
    return ans;
}

循环到 i < n 即可，因为目标是覆盖到 n，不需要在 n 位置再开启水龙头。

六、用数字例子推演

n=5, ranges=[3,4,1,1,0,0]：

i=0 覆盖 [0,3]
i=1 覆盖 [0,5]
i=2 覆盖 [1,3]
i=3 覆盖 [2,4]

maxReach[0]=5，从 0 开始一次就能覆盖到 5，所以答案是 1。

七、常见误区与追问

误区：按水龙头位置顺序直接开启。 位置顺序不是选择依据，覆盖右端才是关键。
误区：忘记截断左右边界。 区间不能超出 [0,n] 的语义范围。
误区：到 n 还继续加答案。 覆盖到 n 后就完成了。
追问：为什么能压成 maxReach？ 同一左端只关心最远右端，较短区间不会更优。
追问：和视频拼接区别是什么？ 本质相同，都是最少区间覆盖目标线段。
追问：复杂度为什么是 O(n)？ 构造和扫描都只走一遍长度 n+1。

八、加强记忆

最少水龙头别按水龙头本身想，先把它变成覆盖区间。之后就按最少区间覆盖做：当前范围内找最远右端，走到边界就必须开一个，把边界推远。curEnd 是当前层，nextEnd 是下一层，推不动就是断档。

简化版

详细版