What is the core pattern for solving Minimum Number of Taps to Open to Water a Garden?

The key pattern is state transition dynamic programming applied to interval coverage, often combined with a greedy selection for efficiency.

How do I handle taps with zero range in this problem?

Taps with zero range do not contribute coverage, so your DP and greedy interval selection must skip them to avoid false coverage assumptions.

Is sorting intervals necessary for the optimal solution?

Yes, sorting intervals by their left endpoint allows the greedy selection to extend coverage correctly and ensures DP updates are efficient.

Can this problem be solved purely with a greedy approach?

In some cases, greedy alone works, but for overlapping or partially disconnected intervals, DP ensures minimal taps, handling complex state transitions.

What should I do if the garden cannot be fully watered?

Return -1. This occurs when intervals do not fully cover the garden, a common failure mode that GhostInterview flags during analysis.

#1326

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

在 x 轴上有一个一维的花园。花园长度为 n ，从点 0 开始，到点 n 结束。花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i…

数组动态规划贪心

题目描述

在 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

lightbulb

解题思路

方法一：贪心

我们注意到，对于所有能覆盖某个左端点的水龙头，选择能覆盖最远右端点的那个水龙头是最优的。

因此，我们可以先预处理数组 $ranges$ ，对于第 $i$ 个水龙头，它能覆盖的左端点 $l = \max(0, i - ranges[i])$ ，右端点 $r = i + ranges[i]$ ，我们算出所有能覆盖左端点 $l$ 的水龙头中，右端点最大的那个位置，记录在数组 $last[i]$ 中。

然后我们定义以下三个变量，其中：

变量 $ans$ 表示最终答案，即最少水龙头数目；
变量 $mx$ 表示当前能覆盖的最远右端点；
变量 $pre$ 表示上一个水龙头覆盖的最远右端点。

我们在 $[0,...n-1]$ 的范围内遍历所有位置，对于当前位置 $i$ ，我们用 $last[i]$ 更新 $mx$ ，即 $mx = \max(mx, last[i])$ 。

如果 $mx \leq i$ ，说明无法覆盖下一个位置，返回 $-1$ 。
如果 $pre = i$ ，说明需要使用一个新的子区间，因此我们将 $ans$ 加 $1$ ，并且更新 $pre = mx$ 。

遍历结束后，返回 $ans$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为花园的长度。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        last = [0] * (n + 1)
        for i, x in enumerate(ranges):
            l, r = max(0, i - x), i + x
            last[l] = max(last[l], r)

        ans = mx = pre = 0
        for i in range(n):
            mx = max(mx, last[i])
            if mx <= i:
                return -1
            if pre == i:
                ans += 1
                pre = mx
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + k) where n is garden length and k is number of intervals after conversion, dominated by sorting and DP updates. Space complexity is O(n) for the DP array to track minimum taps for each point.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The problem tests your ability to model ranges as intervals and optimize coverage efficiently.
question_mark
Expect follow-up questions about greedy versus dynamic programming trade-offs in state transitions.
question_mark
Watch for edge cases with zero ranges or fully overlapping taps.

warning

常见陷阱

外企场景

error
Failing to cap intervals within [0, n], leading to index errors.
error
Not handling intervals that do not fully connect, producing incorrect -1 results.
error
Ignoring overlapping ranges which may cause suboptimal tap selections if not using DP.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum garden length that can be watered with a fixed number of taps using similar interval logic.
arrow_right_alt
Calculate minimum taps needed if taps can only be activated consecutively, introducing extra DP constraints.
arrow_right_alt
Consider varying water pressure limits, effectively changing range intervals dynamically during DP updates.

help

常见问题

外企场景

继续练习

#1363 形成三的最大倍数 #1388 3n 块披萨 #1262 可被三整除的最大和