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

难度: Hard

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

Submission

运行时间: 36 ms

内存: 16.3 MB

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # 设取达到最小值的区间为[a1,b1],...[ak,bk], 这些区间具有如下性质
        # 不妨设1. a1<a2<...<ak, a1<=0
        # 那么2. b1<b2<...<bk 且 ai<b(i-1)
        # 而且 3. bk>=n
        # 下面考察给定k时,满足上述1,2 的所有区间的bk的最大值
        # 为此我们将 b1,b2,...bk存储在一个动态数组a中
        # 再依次更新a,注意a一定是严格递增的
        a=[0]
        ans=inf
        for i in range(n+1):
            l = i-ranges[i]
            r = i+ranges[i]
            if l <= a[-1] < r:
                while len(a)>=2 and l<=a[-2]:
                    a.pop()
                a.append(r)
                if r>=n:
                    ans=min(ans,len(a)-1) 
        return ans if ans<inf else -1

Explain

此题解采用的是贪心策略，核心思想在于通过动态地调整灌溉范围的端点，以最小化所需的水龙头数量。对于每一个水龙头，我们计算其能灌溉的最远范围（左端点和右端点）。随着遍历的进行，如果遇到一个水龙头的左端点不超过当前已覆盖的最远右端点，并且该水龙头的右端点超过了当前最远覆盖范围，我们则更新灌溉范围的右端点。这种方式可以确保每次更新都能尽可能地延伸覆盖范围，从而使用最少数量的水龙头覆盖整个花园。

时间复杂度: O(n)

空间复杂度: O(n)

# 通过计算各水龙头的覆盖范围并选择最佳覆盖进行解题

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # 初始化数组a来记录灌溉的最远端点
        a = [0]
        # 初始化最小水龙头数为无穷大，用于比较
        ans = inf
        # 遍历每一个水龙头位置i
        for i in range(n+1):
            # 计算当前水龙头的左右灌溉范围
            l = i - ranges[i]
            r = i + ranges[i]
            # 如果当前水龙头可以扩展已有的覆盖范围
            if l <= a[-1] < r:
                # 当前水龙头的左端点在上一个覆盖区间内，可能需要更新a
                while len(a) >= 2 and l <= a[-2]:
                    a.pop()  # 移除不再需要的端点
                a.append(r)  # 添加新的最远覆盖点
                # 如果当前覆盖点已经到达或超过花园的末端
                if r >= n:
                    # 更新所需最小水龙头数
                    ans = min(ans, len(a) - 1)
        # 检查是否有有效覆盖，否则返回-1
        return ans if ans < inf else -1

Explore

在算法实现中，这一条件是通过比较当前水龙头的左端点`l`与数组`a`中最后一个元素`a[-1]`来进行判断的。数组`a`记录了当前已经覆盖的最远端点。如果`l`（当前水龙头的左端点）小于或等于`a[-1]`（已覆盖的最远端点），则表示当前水龙头的灌溉范围可以与已有的覆盖范围连续或部分重叠，从而可能扩展当前的覆盖范围。这样的判断确保了每个被选择的水龙头都能实际对花园的灌溉覆盖范围做出贡献。

在更新灌溉范围的右端点时，移除不再需要的端点是为了减小维护的数据规模并保持数组`a`的简洁，这有助于减少不必要的计算和存储开销。具体来说，如果新的水龙头的左端点`l`小于或等于数组`a`中倒数第二个元素`a[-2]`，则意味着新的覆盖范围完全包含或扩展了前一个水龙头的覆盖范围，此时前一个水龙头的记录就变得冗余，因此可以安全地移除。这种操作保证了数组`a`中的每一个端点都是必要的，且代表了使用最少水龙头达到的最远覆盖点，从而确保算法的效率和最终结果的最优性。

数组`a`在算法中扮演了关键的角色，它用来记录在每一步选择中所能达到的最远覆盖范围的端点。在算法开始时，初始化为`[0]`表示从花园的起点开始。随着算法的进行，每当遇到一个新的水龙头，若该水龙头能够扩展当前的覆盖范围（即它的左端点在`a[-1]`之前），则会计算其右端点。如果这个右端点比`a[-1]`更远，就会将它添加到数组`a`中。同时，如果新的左端点`l`小于数组中之前的端点，那些端点会被逐一移除，因为它们的覆盖范围已被新的端点覆盖或包含。这样的操作保证了数组中的端点总是当前选择的水龙头能够覆盖的最远端点，且数组长度反映了所需的最小水龙头数量。