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

链接：1326.灌溉花园的最少水龙头数目
难度：Hard
标签：贪心、数组、动态规划
简介：请你返回可以灌溉整个花园的 最少水龙头数目 。

题解 1 - cpp

• 编辑时间：2023-02-21
• 执行用时：16ms
• 内存消耗：14.3MB
• 编程语言：cpp
• 解法介绍：贪心，对每个起点找尽可能远的终点。

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> list(n + 1, -1);
        for (int i = 0; i < n + 1; i++) {
            int start = max(i - ranges[i], 0), end = min(i + ranges[i], n);
            list[start] = max(list[start], end);
        }
        int cnt = 0, prev = 0, last = 0;
        for (int i = 0; i < n; i++) {
            last = max(last, list[i]);
            if (last == i) return -1;
            if (i == prev) cnt++, prev = last;
        }
        return cnt;
    }
};

题解 2 - rust

• 编辑时间：2023-02-21
• 执行用时：4ms
• 内存消耗：2.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut l = vec![0; n + 1];
        for i in 0..ranges.len() {
            let start = 0.max(i as i32 - ranges[i]) as usize;
            let end = (n as i32).min(i as i32 + ranges[i]) as usize;
            l[start] = l[start].max(end);
        }
        let (mut res, mut pre, mut last) = (0, 0, 0);
        for i in 0..n {
            last = last.max(l[i]);
            if last == i {
                return -1;
            }
            if i == pre {
                res += 1;
                pre = last
            }
        }
        res
    }
}

题解 3 - python

• 编辑时间：2023-02-21
• 执行用时：84ms
• 内存消耗：15.3MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        l = [-1] * (n + 1)
        for i in range(len(ranges)):
            start = max(i - ranges[i], 0)
            end = min(i + ranges[i], n)
            l[start] = max(l[start], end)
        cnt = prev = last = 0
        for i in range(n):
            last = max(last, l[i])
            if last == i:
                return -1
            if i == prev:
                prev = last
                cnt += 1
        return cnt