用C ++打开花园浇水的最小水龙头数量
我们必须找到打开整个花园的水龙头的最小数量，如果没有可能的解决方案，则返回-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：=下一个
（增加ret1）
返回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