企业官网建设流程全解析

题目

在 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] 。

题解

这道题可以用动态规划解，也可以用贪心算法解，贪心思路：在灌溉的开始区域相同的情况下，选择结束区域最远的水龙头打开，这样就可以保证用最少的水龙头灌溉花园。

class Solution { public int minTaps(int n, int[] ranges) { int[] rightMost = new int[n + 1]; for (int i = 0; i <= n; i++) { rightMost[i] = i; } for (int i = 0; i <= n; i++) { int start = Math.max(0, i - ranges[i]); int end = Math.min(n, i + ranges[i]); //计算：灌溉开始区间一样的情况下可以灌溉的最远结束区间 rightMost[start] = Math.max(rightMost[start], end); } int last = 0, ret = 0, pre = 0; for (int i = 0; i < n; i++) { last = Math.max(last, rightMost[i]); //i == last说明这个地方水龙头覆盖不到 if (i == last) { return -1; } if (i == pre) { //需要的水龙头数++ ret++; //下一次需要灌溉的开始区间 pre = last; } } return ret; } }