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

发布时间 2023-04-08 17:56:11作者: lxy_cn

题目链接: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)\)