class Solution {
    public int trap(int[] height) {
        int n = height.length;

        Stack<Integer> left = new Stack<>();
        Stack<Integer> right = new Stack<>();
        int sz = 0, hsum = 0;

        int leftsum = 0;
        int leftMaxId = 0;
        sz = 0; hsum = 0;
        for (int i = 0; i < n; i++) {
            if (left.isEmpty()) {
                left.push(height[i]);
                leftMaxId = i;
                continue;
            }
            
            if (left.peek() < height[i]) {
                leftsum += left.peek() * sz - hsum;
                left.push(height[i]);
                leftMaxId = i;
                sz = 0; hsum = 0;
                continue;
            }

            sz++;
            hsum += height[i];
        }

        int rightsum = 0;
        int rightMaxId = 0;
        sz = 0; hsum = 0;
        for (int i = n-1; i >= 0; i--) {
            if (right.isEmpty()) {
                right.push(height[i]);
                rightMaxId = i;
                continue;
            }

            if (right.peek() < height[i]) {
                rightsum += right.peek() * sz - hsum;
                right.push(height[i]);
                rightMaxId = i;
                sz = 0; hsum = 0;
                continue;
            }

            sz++;
            hsum += height[i];
        }

        int answer = leftsum + rightsum;
        for (int i = leftMaxId+1; i <= rightMaxId-1; i++) {
            answer += left.peek() - height[i];
        }
        return answer;
    }
}