在 x 軸上有一個一維的花園∥嫫耄花園長度為 n蛮放，從點 0 開始，到點 n 結(jié)束奠宜。
花園里總共有 n + 1 個水龍頭包颁，分別位于 [0, 1, ..., n] 。
給你一個整數(shù) n 和一個長度為 n + 1 的整數(shù)數(shù)組 ranges 挎塌，其中 ranges[i] （下標(biāo)從 0 開始）表示：如果打開點 i 處的水龍頭徘六，可以灌溉的區(qū)域為 [i - ranges[i], i + ranges[i]] 。
請你返回可以灌溉整個花園的 最少水龍頭數(shù)目 榴都。如果花園始終存在無法灌溉到的地方待锈，請你返回 -1 。
示例 1：
輸入：n = 5, ranges = [3,4,1,1,0,0]
輸出：1
解釋：
點 0 處的水龍頭可以灌溉區(qū)間 [-3,3]
點 1 處的水龍頭可以灌溉區(qū)間 [-3,5]
點 2 處的水龍頭可以灌溉區(qū)間 [1,3]
點 3 處的水龍頭可以灌溉區(qū)間 [2,4]
點 4 處的水龍頭可以灌溉區(qū)間 [4,4]
點 5 處的水龍頭可以灌溉區(qū)間 [5,5]
只需要打開點 1 處的水龍頭即可灌溉整個花園 [0,5] 嘴高。
示例 2：
輸入：n = 3, ranges = [0,0,0,0]
輸出：-1
解釋：即使打開所有水龍頭竿音，你也無法灌溉整個花園。
示例 3：
輸入：n = 7, ranges = [1,2,1,0,2,1,0,1]
輸出：3
示例 4：
輸入：n = 8, ranges = [4,0,0,0,0,0,0,0,4]
輸出：2
示例 5：
輸入：n = 8, ranges = [4,0,0,0,4,0,0,0,4]
輸出：1
提示：
1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有拴驮。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)春瞬，非商業(yè)轉(zhuǎn)載請注明出處。
解題：解題方法來自leetcode大佬套啤，自己想的方法并未實現(xiàn)所有的ac宽气。
貪心：
在區(qū)間[0,n]中，有n+1個曉得區(qū)間段潜沦，需要從中選擇盡量少的區(qū)間段來可以覆蓋住整個區(qū)間萄涯。區(qū)間該如何選擇，什么樣的區(qū)間改舍棄掉唆鸡，首先必須選擇可以到達終點的區(qū)間涝影，但是這樣的節(jié)點可能會有很多個，那么我們肯定是祖安澤最長的那個争占。按照這樣的思路燃逻，選擇下面的序目。
public int minTaps(int n, int[] ranges) {
public int minTaps(int n, int[] ranges) {
int[] dp = new int[n+1];
int count=0;
int point=0;//標(biāo)記下一個開始端點
int tem=0;
int maxr=0;//最大右端點
for(int i =0;i<ranges.length;i++){//j將區(qū)間表示出來dp[i]表示從i能到達的最遠的距離
tem=dp[Math.max(0,i-ranges[i])];
dp[Math.max(0,i-ranges[i])]=Math.max(tem,Math.min(n,i+ranges[i]));
}
for(int i=0;i<n;i++){
maxtr=Math.max(maxr,dp[i]);//找出最大右端點
if(i==point){//遍歷到最大右端點為起點為止，更新完下一個最大右端點伯襟，計數(shù)加一
if(i>=maxr){
return -1;
}
count++;
point=maxr;
}
}
return count;
}
