假设在x轴上有一维花园。花园的开始位置为0，结束位置为n。花园中的点[0，1，...，n]上有n + 1水龙头。如果我们有一个整数n和一个长度为n + 1的整数数组，其中range [i]是第i个抽头，则当区域为[i-range [i]，i + range [i]]时，可以对该区域进行浇水打开。
我们必须找到打开整个花园的水龙头的最小数量，如果没有可能的解决方案，则返回-1。
因此，如果输入为n = 5，范围= [3,4,1,1,1,0]，则输出为1，从第二次抽头开始，它将覆盖整个地面[-3至5]。
为了解决这个问题，我们将遵循以下步骤-
为了解决这个问题，我们将遵循以下步骤-
定义大小为（n + 1）的数组v并用-1填充
对于初始化i：= 0，当i <= n时，更新（将i增加1），请执行-
u：= i的最大值-range [i]和0
e：= n和i +范围的最小值[i]
v [u]：= v [u]和e的最大值
如果v [0]与-1相同，则-
返回-1
curr：= v [0]
i：= 0，下一个：= 0
而curr <n时，执行-
返回-1
下一个：=下一个和v [i]的最大值
（将i增加1）
当我<= curr时，做-
如果next与curr相同，则-
curr：=下一个
（增加ret 1）
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
int ret = 1;
vector<int> v(n + 1, -1);
for (int i = 0; i <= n; i++) {
int u = max(i - ranges[i], 0);
int e = min(n, i + ranges[i]);
v[u] = max(v[u], e);
}
if (v[0] == -1)
return -1;
int curr = v[0];
int i = 0;
int next = 0;
while (curr < n) {
while (i <= curr) {
next = max(next, v[i]);
i++;
}
if (next == curr)
return -1;
curr = next;
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,4,1,1,1,0};
cout << (ob.minTaps(5, v));
}5, {3,4,1,1,1,0}输出结果
1