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

Posted on | In |
Words count in article: 511 | Reading time ≈ 2

在 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
2
3
4
5
6
7
8
9
10
输入：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] 。

分析：

1
2
3
由于花园的长度为n，可以将问题转化为选择最少的水龙头覆盖整个区间
做法：
	按照左端点排序，假设当前覆盖到的区间右端点为ed，只需要满足选择的子区间的左端点小于ed同时尽可能使ed变的更大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int, int>> r(n + 1);
        for (int i = 0;i <= n;i ++)
            r[i] = make_pair(max(0, i - ranges[i]), min(ranges[i] + i, n));

        sort(r.begin(), r.end());

        int i = 0, ed = 0;
        int res = 0;
        while (i <= n && ed < n) {
            int next_ed = 0; // 下一次的覆盖末端点
            while (i <= n && r[i].first <= ed) {
                next_ed = max(next_ed, r[i].second);
                i ++;
            }

            if (ed == next_ed) return -1; // 当ed == nexted 时无法在选择新区间

            res ++;
            ed = next_ed;
        }

        return res;
    }
};

[原题链接](1326. 灌溉花园的最少水龙头数目 - 力扣（Leetcode）)

0%