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

题目链接：1326. 灌溉花园的最少水龙头数目

方法：贪心

解题思路

每次到达端点l时，寻找在此处能够到达的最远右端点；
思路一： 先对每个水龙头能够覆盖的 \([l, r]\) 构成的数组 \(rg\) 按照 \(l\) 进行从小到大排序，然后遍历右端点 \(r=[0, n]\)，对于当前 \(r\)，在 \(rg\) 中找其能够到达的下一个最右端点，若不存在，则返回 \(-1\)，否则继续遍历右端点，最后输出 \(cnt\)；
思路二： 对 \(ranges\) 数组进行预处理，创建 \(last\) 数组，\(last[i]\) 表示从 \(i\) 处开始能够覆盖的最远右端点。然后遍历右端点 \(r=[0, n]\)，对于当前 \(r\)，在 \(last\) 中找其能够到达的下一个最右端点，若不存在，则返回 \(-1\)，否则继续遍历右端点，最后输出 \(cnt\)；

代码一

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int, int>> rg(n + 1); // rg[i]表示i处水龙头的灌溉区域[first, second]
        for (int i = 0; i < ranges.size(); i ++ ) {
            rg[i].first = i - ranges[i];
            rg[i].second = i + ranges[i];
        }
        sort(rg.begin(), rg.end()); // 默认先根据rg[i].first从小到大排序
        int r = 0, i = 0;
        int cnt = 0;
        while (r < n) {
            int mx = -1;
            while (i < rg.size() && rg[i].first <= r) { // 当前右端点能覆盖i水龙头的左端点
                mx = max(mx, rg[i].second);
                i ++ ;
            }
            if (mx == -1) return -1; // 没找到比当前右端点更远的右端点
            r = mx;
            cnt ++ ;
        }
        return cnt;
    }
};

复杂度分析

时间复杂度：\(O(nlogn)\)；
空间读杂度：\(O(n)\)。

代码二

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> last(n + 1);
        for (int i = 0; i < ranges.size(); i ++ ) {
            int l = max(0, i - ranges[i]), r = min(n, i + ranges[i]); // 左端点小于0 || 右端点大于n 无意义
            last[l] = max(last[l], r);
        }
        int cnt = 0, r = 0, i = 0;
        while (r < n) {
            int mx = -1;
            while (i < n && r >= i) { // 当前右端点能覆盖i处
                if (last[i] > r) mx = max(mx, last[i]); 
                i ++ ; // 若last[i] <= r此时没有超过当前右端点，直接 i ++
            }
            if (mx == -1) return -1; // 没找到比当前右端点更远的右端点
            cnt ++ ;
            r = mx;
        }
        return cnt;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间读杂度：\(O(n)\)。