Manjusaka

08-30 leetcode-1326

链接 1326. Minimum Number of Taps to Open to Water a Garden

又是一个 Hard，还是一个贪心 Hard，麻了

题目

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, …, n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

题解

这题最直接的一个做法是用一个数组，在每个点记录可以到达的最远的位置

然后从0出发，看能到达的最远的位置是否覆盖全部花园。

class Solution:
    def minTaps(self, n: int, ranges: list[int]) -> int:
        index = [0] * (n + 1)
        for i in range(n + 1):
            start, end = max(0, i - ranges[i]), min(n + 1, i + ranges[i])
            for j in range(start, end):
                index[j] = max(index[j], end)
        result, position = 0, 0
        while position < n:
            if index[position] <= position:
                return -1
            position = index[position]
            result += 1
        return result