灌溉花园的最少水龙头数目

08 Sep 2024 in Algorithm Pageviews

blabla

在 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:

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

输出：1

解释：

点 0 处的水龙头可以灌溉区间 [-3, 3]

点 1 处的水龙头可以灌溉区间 [-3, 5]

点 2 处的水笼头可以灌溉区间 [1, 3]

点 3 处的水龙头可以灌溉区间 [2, 4]

点 4 处的水龙头可以灌溉区间 [4, 4]

点 5 处的水龙头可以灌溉区间 [5, 5]

只需要打开点 1 处的水龙头即可灌溉整个花园 [0, 5]

示例2：

输入：n = 3, ranges = [0, 0, 0, 0]

输出：-1

解释：即使打开所有的水龙头，你也无法灌溉整个花园。

代码实现如下:

class Solution {
public:
    int MinTaps(int n, vector<int> &ranges)
    {
        vector<int> maxRight(n + 1);
        std::generate(maxRight.begin(), maxRight.end(), [i = 0]() mutable {return i++;});
        for (int i = 0; i <= n; i++) {
            int l = max(0, i - ranges[i]);
            int r = min(n, i + ranges[i]);
            for (int j = l; j <= r; j++) {
                maxRight[j] = max(maxRight[j], r);
            }
        }
        
        int r = 0;
        int cnt = 0;
        while (r < n) {
            if (r == maxRight[r]) {
                return -1;
            }
            
            r = maxRight[r];
            ++cnt;
        }
        return cnt;
    }
};