题目链接：1326. 灌溉花园的最少水龙头数目
方法：贪心
解题思路
每次到达端点l时，寻找在此处能够到达的最远右端点；
思路一： 先对每个水龙头能够覆盖的 \([l, r]\) 构成的数组 \(rg\) 按照 \(l\) 进行从小到大排序，然后遍历右端点 \(r=[0, n]\)，对于当前 \(r\)，在 \(rg\) 中找其能够到达的下一个最右端点，若不存在，则返回 \(-1\)，否则继续遍历右端点，最后输出 \(cnt\)；
思路二： 对 \(ranges\) 数组进行预处理，创建 \(last\) 数组，\(last[i]\) 表示从 \(i\) 处开始能够覆盖的最远右端点。然后遍历右端点 \(r=[0, n]\)，对于当前 \(r\)，在 \(last\) 中找其能够到达的下一个最右端点，若不存在，则返回 \(-1\)，否则继续遍历右端点，最后输出 \(cnt\)；
代码一
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<pair<int, int>> rg(n + 1); // rg[i]表示i处水龙头的灌溉区域[first, second]
for (int i = 0; i < ranges.size(); i ++ ) {
rg[i].first = i - ranges[i];
rg[i].second = i + ranges[i];
}
sort(rg.begin(), rg.end()); // 默认先根据rg[i].first从小到大排序
int r = 0, i = 0;
int cnt = 0;
while (r < n) {
int mx = -1;
while (i < rg.size() && rg[i].first <= r) { // 当前右端点能覆盖i水龙头的左端点
mx = max(mx, rg[i].second);
i ++ ;
}
if (mx == -1) return -1; // 没找到比当前右端点更远的右端点
r = mx;
cnt ++ ;
}
return cnt;
}
};
复杂度分析
时间复杂度：\(O(nlogn)\)；
空间读杂度：\(O(n)\)。
代码二
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> last(n + 1);
for (int i = 0; i < ranges.size(); i ++ ) {
int l = max(0, i - ranges[i]), r = min(n, i + ranges[i]); // 左端点小于0 || 右端点大于n 无意义
last[l] = max(last[l], r);
}
int cnt = 0, r = 0, i = 0;
while (r < n) {
int mx = -1;
while (i < n && r >= i) { // 当前右端点能覆盖i处
if (last[i] > r) mx = max(mx, last[i]);
i ++ ; // 若last[i] <= r此时没有超过当前右端点，直接 i ++
}
if (mx == -1) return -1; // 没找到比当前右端点更远的右端点
cnt ++ ;
r = mx;
}
return cnt;
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间读杂度：\(O(n)\)。