leetcode

0 class Solution {

1 public:

2 int minTaps(int n, const vector<int> &ranges) {

3 vector<int> reach(n + 1);

4 for (int i = 0; i < ranges.size(); i++) {

5 int start = max(i - ranges[i], 0);

6 int end = min(n, i + ranges[i]);

7 reach[start] = max(reach[start], end);

8 }

9

10 int res = 0, crnt = 0, next = 0;

11 for (int i = 0; i <= n; i++) {

12 if (i > next) return -1;

13 if (i > crnt) {

14 res++;

15 crnt = next;

16 }

17 next = max(next, reach[i]);

18 }

19

20 return res;

21 }

22 };