题目大意：
灌溉花园的最少水龙头数目
在 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 解释：即使打开所有水龙头，你也无法灌溉整个花园。
示例 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^4ranges.length == n + 10 <= ranges[i] <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1326
解题思路分析：
本题一开始想到的是使用递归思路，首层递归，循环整个花园从左至右所有的喷头，当前喷头的覆盖范围需要一个cost，当前喷头范围左边界到当前递归总范围的左边，以及当前喷头范围的右边界到当前递归总范围的右边，递归到子问题求解。两个子问题的解加一即是当前解，循环所有喷头后计算一个最小解即是当前递归的最优解。
然而提交后发现这种解法效率很低，处于TLE的边缘。于是想到了下面这种贪心算法。
首先我们算出每个喷头的范围left和right，如果left小于0，记为0，如果right大于n，记为n。我们将每个范围看作是一个线段或者区间，将区间存入一个数组maxRange[]，数组下标为该区间的left，该下标的值为区间的right。循环时，如果遇到相同left下标的值已经存在于maxRange[left]时，更新最大值存入，即代表始于当前left的区间，最远能够达到right位置。
这时问题就变的简单了，我们只需要在一堆线段中，找出最少能覆盖整个区域的线段数即可。从left为0开始找，此时maxRange[0]代表0开始的线段最远能到达的index。接下来，我们需要在[left+1, maxRange[left]]范围内一条能够到达的最远的线段即可，如果该最远线段小于等于当前maxRange[left]，说明与当前相交的所有线段中没有能够超越maxRange[left]点的线段了，因此返回-1。反之继续向后寻找，直到找到某条线段能到达终点为止。
实现代码：
public int minTaps(int n, int[] ranges) {
// 所有喷头覆盖的区间
int[] maxRanges = new int[n+1];
// 循环每一个喷头
for(int i=0;i<ranges.length;i++){
// 喷头覆盖区间的左下标
int left=i-ranges[i];
// 左下标小于0时，设为0
if(left<0) left=0;
// 喷头覆盖区间的右下标
int right=i+ranges[i];
// 右下标大于n时，设为n
if(right>n) right=n;
// 将区间存入maxRanges
// maxRanges[left]代表左下标为left的区间最远可以到达的坐标
maxRanges[left] =Math.max(maxRanges[left], right);
}
// 找出能够覆盖整个区间的最少区间个数
// 第一个区间从0开始，maxRanges[0]结束
int l=0,r=maxRanges[0];
int res=1; // 返回结果
// 当右区间小于n时循环
while(r<n){
// 找到下一个区间，下一个区间的left在当前区间内
// 并且下一个区间的right大于当前区间right
// 找到符合上述要求的一个right最大区间
int maxRight=r;
int maxLeft=l;
for(int i=l;i<=r;i++){
if(maxRanges[i]>maxRight){
maxRight=maxRanges[i];
maxLeft=i;
}
}
// 如果最大right不能大于当前right，返回-1
if(maxRight==r) return -1;
// 更新下一个区间的left和right
r=maxRight;
l=maxLeft+1;
res++;
}
return res;
} 本题解法执行时间为2ms。
Runtime: 3 ms, faster than 100.00% of Java online submissions for Minimum Number of Taps to Open to Water a Garden.
Memory Usage: 47.2 MB, less than 100.00% of Java online submissions for Minimum Number of Taps to Open to Water a Garden.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1326-minimum-number-of-taps-to-open-to-water-a-garden-解题思路分析/