1326. 灌溉花园的最少水龙头数目
在 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
解释：即使打开所有水龙头，你也无法灌溉整个花园。
提示：
1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100解答：排序+双指针
class Solution {
public int minTaps(int n, int[] ranges) {
int[][] res=new int[n+1][2];
for(int i=0;i<=n;i++){
res[i][0]=i-ranges[i];
res[i][1]=i+ranges[i];
}
Arrays.sort(res,(a,b)->a[0]-b[0]);
//r表示右区间
int ans=0,r=0;
for(int i=0;i<=n;i++){
//curr表示现在的右区间
int j=i,curr=-1;
//当j在范围内，并且现在的左区间要<=上一个右区间r
while(j<=n&&res[j][0]<=r){
//找到一个满足左边界<=上一个右区间r的最大右边界
curr=Math.max(curr,res[j++][1]);
}
//找不到下一个最近的点
if(curr==-1)return -1;
ans++;
//已经全部覆盖
if(curr>=n)return ans;
r=curr;
i=j-1;
}
//无法覆盖全部区间
return -1;
}
}
