Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int h[100005], sums[100005], fle[100005];
- int trap(vector<int>& height) {
- int n = height.size();
- for(int i = 1; i <= n; ++i) {
- h[i] = height[i - 1];
- sums[i] = sums[i - 1] + h[i];
- }
- fle[1] = 1;
- int best = 0;
- for (int i = 2; i <= n; ++i) {
- int idx = i - 1;
- while (idx > 0 && fle[idx] != idx && h[idx] < h[i]) {
- idx = fle[idx];
- }
- if(h[idx] >= h[i]) fle[i] = idx;
- else fle[i] = i;
- best = max(best, (i - idx - 1) * min(h[i], h[idx]) - (sums[i - 1] - sums[idx]));
- }
- return best;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement