【Leetcode 每日一题 - 扩展】1326. 灌溉花园的最少水龙头数目-具体实现

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;
    }
}