题目描述

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, …, n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -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] 。

算法1

动态规划

dp[i]表示把0~i的地都覆盖的水龙头的最少数目。在遍历num数组的过程中计算出这个水龙头浇灌的范围left ~ right，那么dp[right] = min(dp[left + 1], dp[left + 2], ......, dp[right - 1).
边界条件和初始化：初始化dp元素都为INF，dp[0] = 0；

时间复杂度

$ O(n * range) $

C++ 代码

const int N = 10010, INF = 0x3f3f3f3f;
int dp[N];
class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for(int i = 0; i <= n; i++){
            int r = ranges[i];
            int left = max(0, i - r), right = min(n, i + r);//计算范围
            for(int j = left; j < right; j++){
                dp[right] = min(dp[right], dp[j] + 1);//找到dp[right]的最少水龙头数
            }
        }
        if(dp[n] == INF) return -1;//无法浇灌
        else return dp[n];
    }
};

算法2

贪心

贪心的做法类似于这道题：https://www.acwing.com/solution/leetcode/content/7750/
这道题的本质是区间覆盖，所以把每个水龙头可以浇灌的区间计算出来，然后按照区间覆盖的算法进行计算即可。

区间覆盖

0.确定要覆盖的区间范围[l, r]
1.将所有区间按照左端点进行排序
2.在左端点$l_i$ <= end的所有区间中找到$r_i$最大的右端点（贪心），然后扩展end。如果end能够扩展到r，则表示可以覆盖这个区间。输出结果，如果扩展不到，则表示[l, r]内有区间不能被覆盖。
主要思想如上，还需要res记录区间个数。细节见代码

时间复杂度

初始化数组：$O(n)$
排序：$O(nlogn)$
贪心:$O(n)$
所以算法的时间复杂度是$O(nlogn)$

C++代码

typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
class Solution {
public:

    int minTaps(int n, vector<int>& ranges) {
        int l = 0, r = n;//确定覆盖的区间的左右端点
        vector<PII> segs;
        for(int i = 0; i<=n; i++)
            segs.push_back({i - ranges[i], i + ranges[i]});//将水龙头的灌溉范围处理成区间
        sort(segs.begin(), segs.end());//将区间按照左端点进行排序
        int res = 0, end = l, i = 0, cur;
        while(end < r){//当end被扩展到r时，结束
            cur = -INF;
            while(i <= n && segs[i].first <= end) cur = max(cur, segs[i ++ ].second);//在满足条件的区间中找到最大的右端点
            if(cur == -INF){//如果没有满足条件的区间，表示end不能进行扩展
                res = -1;
                break;//退出循环
            }
            res ++ ;//区间数加1
            end = cur;//用cur扩展end
        }
        return res;
    }
};
};