跳到主要内容

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

· 阅读需 4 分钟

1、题干​

在 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 <= 104
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100

写了个奇怪的动态规划思路

2、思路​

用 [i-r,i) 区间的最少水龙头数更新 dp[i]，用 dp[i] 更新 (i,i+r] 区间的最少水龙头数。

dp 数组元素有正负两种状态，正数表示自身可以达到最少水龙头数，负数表示被其他水龙头覆盖达到最少水龙头数；负数在更新 (i,i+r] 区间时需要 +1，正数则不需要。

3、代码​

function minTaps(n: number, ranges: number[]): number {
    const dp = ranges.map(() => Infinity);

    for (let i = 0, r = 0; i <= n; i++) {
        r = ranges[i];
        if (i - r < 1) dp[i] = 1;

        for (let j = Math.max(0, i - r); j <= Math.min(n, i + r); j++) {
            const di = Math.abs(dp[i]), dj = Math.abs(dp[j]);
            if (j < i && dj + 1 <= di) dp[i] = dj + 1;
            else if (j > i) {
                if (dp[i] > 0 && di <= dj) dp[j] = -di;
                else if (dp[i] <= 0 && di + 1 <= dj) dp[j] = -di - 1;
            }
        }
    }

    return dp.at(-1) < Infinity ? Math.abs(dp.at(-1)) : -1;
};

4、复杂度​

  • 时间复杂度：O(mn)O(mn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png