【Leetcode 每日一题 - 扩展】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\le n\le 10^4$
• $ranges.length=n+1$
• $0\le ranges[i]\le 100$

解题过程

首先要理解题目给的第二个样例为什么不满足条件，这里灌溉的意思是区间内部（形态是线段的那个部分）也需要覆盖到，所以总体上要当成一个区间着色问题来处理。
这题比较难的是转化的过程，如果不加限制地在数组中按最大值来选择，会出现很多空隙，比较难解决。
考虑在每个位置上，如果可以任意打开一个水龙头，那么它在覆盖到这个位置的前提下，最远能够顾及到什么位置。
比如在下标为 $2$ 这个位置上打开了覆盖范围为 $2$ 的水龙头，可以转化为在 $0$ 这个位置上，有一个水龙头能够覆盖到 $2$ 这个范围（当然这样举例它不一定是最大的）。
这样一来，就可以用类似 跳跃游戏 II 的贪心算法，来搞定这个问题。唯一的区别是这道题没有保证一定有符合条件的答案，所以要单独判断什么时候返回 $-1$。

具体实现

class Solution {
    public int minTaps(int n, int[] ranges) {
        // 定义一个数组来记录每个位置上可能达到的最远边界
        int[] ends = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            int range = ranges[i];
            // 如果超过可达范围，也就是左边最远的地方不会到达下标为 0 的位置，可以直接记录答案
            if(i > range) {
                ends[i - range] = i + range;
            } else {
                ends[0] = Math.max(ends[0], i + range);
            }
        }
        int res = 0;
        int curEnd = 0;
        int nextEnd = 0;
        for(int i = 0; i < n; i++) {
            nextEnd = Math.max(nextEnd, ends[i]);
            if(i == curEnd) {
                // 如果达到了当前所能达到的最远位置，但没有继续延伸的可能，应该返回 -1
                if(i == nextEnd) {
                    return -1;
                }
                curEnd = nextEnd;
                res++;
            }
        }
        return res;
    }
}