class Solution {
    //下标i处能接的雨水为左右两边的最大值里的最小值- height[i]
    // 这里可以用双指针的思想 时间复杂度O(n),空间复杂度O(1)
    // 动态规划更直接， 用两个数组记录左右两边的最大值 时间复杂度O(n),空间复杂度O(1)
    public int trap(int[] height) {
        int n = height.length;
        // int[] leftMax = new int[n];
        // int[] rightMax = new int[n];
        // leftMax[0] = height[0];
        // rightMax[n - 1] = height[n - 1];
        // for (int i = 1; i < n; i++) {
        //     leftMax[i] = Math.max(leftMax[i-1], height[i]);
        // }
        // for (int i = n - 2; i >= 0; i--) {
        //     rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        // }
        // int sum = 0;
        // for (int i = 0; i < n; i++) {
        //     sum += Math.min(leftMax[i], rightMax[i]) - height[i];
        // }
        // return sum;
        int leftMax = 0, rightMax = 0;
        int left = 0,right = n - 1, sum = 0;
        while (left <= right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);
            if (leftMax < rightMax) {
                sum += leftMax - height[left];
                left++;
            } else {
                sum += rightMax - height[right];
                right--;
            }
        }
        return sum;
    }
}