Eric 的小站

1
class Solution {
2
public:
3
    int trap(vector<int>& height) {
4
        int n = height.size();
5
        if (n == 0) {
6
            return 0;
7
        }
8
        vector<int> leftMax(n);
9
        leftMax[0] = height[0];
10
        for (int i = 1; i < n; ++i) {
11
            leftMax[i] = max(leftMax[i - 1], height[i]);
12
        }
13

14
        vector<int> rightMax(n);
15
        rightMax[n - 1] = height[n - 1];
16
        for (int i = n - 2; i >= 0; --i) {
17
            rightMax[i] = max(rightMax[i + 1], height[i]);
18
        }
19

20
        int ans = 0;
21
        for (int i = 0; i < n; ++i) {
22
            ans += min(leftMax[i], rightMax[i]) - height[i];
23
        }
24
        return ans;
25
    }
26
};