Hard

题目描述

在 x 轴上有一个一维花园。花园从点 0 开始，到点 n 结束（即花园的长度为 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]
只需要打开第二个水龙头就可以浇灌整个花园 [0,5]

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使你开启所有的水龙头，你也无法浇灌整个花园。

提示：

  • 1 <= n <= 10^4
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100

解题思路

这是一个经典的区间覆盖问题，我们需要用最少的区间覆盖整个范围 [0, n]。

解题思路：

  1. 区间转换：将每个水龙头的覆盖范围转换为区间 [left, right]，其中第 i 个水龙头覆盖区间为 [max(0, i - ranges[i]), min(n, i + ranges[i])]

  2. 贪心策略：使用贪心算法选择最优的水龙头。对于每个需要覆盖的位置，我们选择能够覆盖该位置且右端点最远的水龙头。

  3. 算法流程：

    • 从位置 0 开始，需要覆盖到位置 n
    • 对于当前位置，找出所有能覆盖该位置的水龙头
    • 选择其中右端点最远的那个
    • 更新当前位置为选中水龙头的右端点
    • 重复直到覆盖完整个花园

这种方法的核心思想是：在保证能够覆盖当前位置的前提下，选择覆盖范围最远的水龙头，这样可以最大化每一步的收益，从而用最少的水龙头覆盖整个花园。

代码实现

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        // 创建区间数组
        vector<pair<int, int>> intervals;
        for (int i = 0; i <= n; i++) {
            int left = max(0, i - ranges[i]);
            int right = min(n, i + ranges[i]);
            if (left <= right) {
                intervals.push_back({left, right});
            }
        }
        
        // 按左端点排序
        sort(intervals.begin(), intervals.end());
        
        int taps = 0;
        int currentPos = 0;
        int i = 0;
        
        while (currentPos < n) {
            int maxReach = currentPos;
            
            // 找到所有能覆盖当前位置的区间中右端点最远的
            while (i < intervals.size() && intervals[i].first <= currentPos) {
                maxReach = max(maxReach, intervals[i].second);
                i++;
            }
            
            // 如果没有进展，说明无法覆盖
            if (maxReach == currentPos) {
                return -1;
            }
            
            taps++;
            currentPos = maxReach;
        }
        
        return taps;
    }
};

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # 创建区间数组
        intervals = []
        for i in range(n + 1):
            left = max(0, i - ranges[i])
            right = min(n, i + ranges[i])
            if left <= right:
                intervals.append([left, right])
        
        # 按左端点排序
        intervals.sort()
        
        taps = 0
        current_pos = 0
        i = 0
        
        while current_pos < n:
            max_reach = current_pos
            
            # 找到所有能覆盖当前位置的区间中右端点最远的
            while i < len(intervals) and intervals[i][0] <= current_pos:
                max_reach = max(max_reach, intervals[i][1])
                i += 1
            
            # 如果没有进展，说明无法覆盖
            if max_reach == current_pos:
                return -1
            
            taps += 1
            current_pos = max_reach
        
        return taps

public class Solution {
    public int MinTaps(int n, int[] ranges) {
        // 创建区间数组
        List<int[]> intervals = new List<int[]>();
        for (int i = 0; i <= n; i++) {
            int left = Math.Max(0, i - ranges[i]);
            int right = Math.Min(n, i + ranges[i]);
            if (left <= right) {
                intervals.Add(new int[] {left, right});
            }
        }
        
        // 按左端点排序
        intervals.Sort((a, b) => a[0].CompareTo(b[0]));
        
        int taps = 0;
        int currentPos = 0;
        int i = 0;
        
        while (currentPos < n) {
            int maxReach = currentPos;
            
            // 找到所有能覆盖当前位置的区间中右端点最远的
            while (i < intervals.Count && intervals[i][0] <= currentPos) {
                maxReach = Math.Max(maxReach, intervals[i][1]);
                i++;
            }
            
            // 如果没有进展，说明无法覆盖
            if (maxReach == currentPos) {
                return -1;
            }
            
            taps++;
            currentPos = maxReach;
        }
        
        return taps;
    }
}

var minTaps = function(n, ranges) {
    const intervals = [];
    
    for (let i = 0; i < ranges.length; i++) {
        const left = Math.max(0, i - ranges[i]);
        const right = Math.min(n, i + ranges[i]);
        if (left <= right) {
            intervals.push([left, right]);
        }
    }
    
    intervals.sort((a, b) => a[0] - b[0]);
    
    let taps = 0;
    let currentEnd = 0;
    let farthest = 0;
    let i = 0;
    
    while (currentEnd < n) {
        while (i < intervals.length && intervals[i][0] <= currentEnd) {
            farthest = Math.max(farthest, intervals[i][1]);
            i++;
        }
        
        if (farthest <= currentEnd) {
            return -1;
        }
        
        taps++;
        currentEnd = farthest;
    }
    
    return taps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要开销在排序区间数组
空间复杂度O(n)存储区间数组的空间