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

        for(int i = 0; i < n; i ++){
            int _min = min(leftMax[i], rightMax[i]);
            if(_min > height[i]) res += _min - height[i];
        }
        return res;
    }
};