灌溉花园的最少水龙头数目
难度:
标签:
题目描述
在 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 <= 104ranges.length == n + 10 <= ranges[i] <= 100
代码结果
运行时间: 36 ms, 内存: 16.3 MB
/*
* 思路：
* 1. 创建一个数组 maxRange，用于存储每个点能够到达的最远距离。
* 2. 使用 Java Stream 计算每个点能覆盖的最大范围，并更新 maxRange。
* 3. 初始化变量 taps 和 currEnd 表示当前打开的水龙头数量和当前能覆盖的最远位置。
* 4. 使用贪心算法遍历 maxRange 数组，更新 currEnd 并在必要时增加水龙头数量。
* 5. 如果在遍历过程中无法继续前进，返回 -1。
*/
import java.util.stream.IntStream;
public class Solution {
public int minTaps(int n, int[] ranges) {
int[] maxRange = new int[n + 1];
IntStream.rangeClosed(0, n).forEach(i -> {
int left = Math.max(0, i - ranges[i]);
int right = Math.min(n, i + ranges[i]);
maxRange[left] = Math.max(maxRange[left], right);
});
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n; i++) {
nextEnd = Math.max(nextEnd, maxRange[i]);
if (i == currEnd) {
if (i == nextEnd) return -1;
currEnd = nextEnd;
taps++;
}
}
return taps;
}
}解释
方法:
此题解采用的是贪心策略，核心思想在于通过动态地调整灌溉范围的端点，以最小化所需的水龙头数量。对于每一个水龙头，我们计算其能灌溉的最远范围（左端点和右端点）。随着遍历的进行，如果遇到一个水龙头的左端点不超过当前已覆盖的最远右端点，并且该水龙头的右端点超过了当前最远覆盖范围，我们则更新灌溉范围的右端点。这种方式可以确保每次更新都能尽可能地延伸覆盖范围，从而使用最少数量的水龙头覆盖整个花园。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，如何确保每个水龙头的左端点不超过当前已覆盖的最远右端点，这一条件是如何判断的？
▷🦆
为什么在更新灌溉范围的右端点时，需要移除不再需要的端点？移除这些端点有什么具体的优势和影响？
▷🦆
算法中使用了一个数组 `a` 来记录覆盖的最远端点，但是代码中似乎并没有详细解释这个数组的详细结构和使用方式。数组 `a` 的具体作用和操作逻辑是什么？
▷