灌溉花园的最少水龙头数目

题目描述

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, …, n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

样例

样例输入

n = 5, ranges = [3,4,1,1,0,0]
n = 3, ranges = [0,0,0,0]

样例输出

1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示

• $1<=n<=10^4$
• $ranges.length==n+1$
• $0<=ranges[i]<=10$

思路

大的总问题可以化为相同类型的子问题，可以使用动态规划。且不仅仅可以使用动态规划，还可以使用贪心思想，因为在相同类型的子问题中，可以取其最优解。

代码实现

动态规划

class Solution {public int minTaps(int n, int[] ranges) {int[][] arr = new int[n+1][2];for(int i = 0; i <= n; i++){arr[i][0] =  Math.max(0, i - ranges[i]);arr[i][1] = Math.min(n, i + ranges[i]);}Arrays.sort(arr, (a, b) -> a[0] - b[0]);int[] dp = new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int[] a : arr){if(dp[a[0]] == Integer.MAX_VALUE) return -1;for(int i = a[0]; i <= a[1]; i++) dp[i] = Math.min(dp[i], dp[a[0]] + 1);}return dp[n];}
}

贪心思想

class Solution {public int minTaps(int n, int[] ranges) {int[] right = new int[n+1];for(int i = 0; i <= n; i++) right[i] = i;for(int i = 0; i < ranges.length; i++){int start = Math.max(0, i - ranges[i]);int end = Math.min(n, i + ranges[i]);right[start] = Math.max(right[start], end);}int last = 0, res = 0, pre = 0;for(int i = 0; i < n; i++){last = Math.max(last, right[i]);if(i == last) return -1;if(i == pre){res++;pre = last;}}return res;}
}