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

## 问题描述
[1326. 灌溉花园的最少水龙头数目 (Hard)](https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/)

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

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

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

请你返回可以灌溉整个花园的 **最少水龙头数目** 。如果花园始终存在无法灌溉到的地方，请你返回 **-1** 。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065405.png)

```
输入：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] 。

```

**示例 2：**

```
输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

```

**提示：**

- `1 <= n <= 10⁴`
- `ranges.length == n + 1`
- `0 <= ranges[i] <= 100`

## 解题思路
### 贪心
假设当前能浇灌的最右端为`end`，对应的水龙头为`start_idx`，那么应该选满足`start[i] <= end`且`end[i]`最大的`i`。在这里，我们构建一个数组`vector<int> right_most(n + 1, 0)`，表示当坐标`i`的点能被浇灌到时，所能浇灌到的最远点。

然后，我们从`0~n`遍历`i`，如果`right_most[i]`大于`next_right`，那么更新`next_right`，原先的`next_right`记为`cur_right`，如果`i == cur_right`了，说明要再开一个水龙头。

### 排序+二分查找
这个做法也是有一点贪心的思路，假设当前能浇灌的最右端为`end`，对应的水龙头为`start_idx`，那么应该选满足`start[i] <= end`且`end[i]`最大的`i`，可以利用二分查找找到满足`start[i] <= end`的`i`的最大值`idx`，然后遍历`[start_idx, idx]`，找最大的`end[i]`,并更新`start_idx`。

### 动态规划
`dp[i]`表示覆盖`[0, i]`所需要的最少水龙头数量；

我们假设`dp[i]`的情况下，打开的最后一个水龙头为`(start[j], end[j])`，那么对于`start[j] < k < end[j]`，`dp[k] = min(dp[k], dp[start[j]] + 1)`，所以这里我们需要将`dp[i]`初始化为一个极大值，并且需要将`water_range`数组按照`start[i]`从小到大排序。


## 代码
### 动态规划
```cpp
class Solution {
  public:
    int minTaps(int n, vector<int> &ranges) {
        vector<vector<int>> water_range;
        for (int i = 0; i <= n; i++) {
            water_range.push_back({std::max(0, i - ranges[i]), std::min(i + ranges[i], n)});
        }
        std::sort(water_range.begin(), water_range.end());
        vector<int> dp(n + 1, 30000);
        dp[0] = 0;
        for(int i = 0; i <= n; i++) {
            if (dp[water_range[i][0]] == 30000)
                return -1;
            for (int j = water_range[i][0]; j <= water_range[i][1]; j++) {
                dp[j] = std::min(dp[j], dp[water_range[i][0]] + 1);
            }
        }
        return dp[n];
    }
};
```

### 贪心
```cpp
class Solution {
public:
    int minTaps(int n, vector<int> &ranges) {
        int right_most[n + 1]; memset(right_most, 0, sizeof(right_most));
        for (int i = 0; i <= n; ++i) {
            int r = ranges[i];
            if (i > r) right_most[i - r] = i + r; // 对于 i-r 来说，i+r 必然是它目前的最大值
            else right_most[0] = max(right_most[0], i + r);
        }

        int ans = 0;
        int cur_right = 0; // 已建造的桥的右端点
        int next_right = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < n; ++i) { // 注意这里没有遍历到 n，因为它已经是终点了
            next_right = max(next_right, right_most[i]);

            if (i == cur_right) { // 到达已建造的桥的右端点
                if (i == next_right) return -1; // 无论怎么造桥，都无法从 i 到 i+1
                cur_right = next_right; // 造一座桥
                ++ans;
            }
        }
        return ans;
    }
};
```

### 排序+二分查找
```cpp
class Solution {
  public:
    // 二分查找
    int Bfind(vector<vector<int>> &vec, int target, int start_idx) {
        int left = start_idx, right = vec.size();
        int mid = left + (right - left) / 2;
        while (left < right) {
            if (vec[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
            mid = left + (right - left) / 2;
        }
        return left;
    }
    int minTaps(int n, vector<int> &ranges) {
        vector<vector<int>> water_range;
        for (int i = 0; i <= n; i++) {
            water_range.push_back({i - ranges[i], i + ranges[i]});
        }
        auto cmp = [&](vector<int> &v1, vector<int> &v2) {
            if (v1[0] == v2[0])
                return v1[1] <= v2[1];
            return v1[0] < v2[0];
        };
        std::sort(water_range.begin(), water_range.end(), cmp);
        int start_idx = 0, end = 0;
        int cnt = 0;
        while (end < n) {
            int idx = Bfind(water_range, end + 1, start_idx) - 1; // 找到满足start[idx] <= end的最大的idx
            for (int i = start_idx; i <= idx; i++) {
                if (water_range[i][1] > end) {
                    start_idx = i;
                    end = water_range[i][1];
                }
            }
            cnt++;
            if (cnt > n)
                return -1;
        }
        return cnt;
    }
};
```