// @Title: 接雨水 (Trapping Rain Water)
// @Author: qisiii
// @Date: 2024-04-28 23:38:22
// @Runtime: 1 ms
// @Memory: 44.9 MB
// @comment: 动态规划，其实严格意思不算，只是提前算了出来
// @flag: WHITE
class Solution {
    public int trap(int[] height) {
        int result=0;
        int n=height.length;
        int[] left=new int[n],right=new int[n];
        left[0]=height[0];right[n-1]=height[n-1];
        for(int i=1;i<n;i++){
            left[i]=Math.max(left[i-1],height[i]);
        }
        for(int i=n-2;i>=0;i--){
            right[i]=Math.max(right[i+1],height[i]);
        }
        for(int i=0;i<n;i++){
            int min=Math.min(left[i],right[i]);
            if(min>height[i]){
                result=result+min-height[i];
            }
        }
        return result;
    }
}

// @Title: 接雨水 (Trapping Rain Water)
// @Author: qisiii
// @Date: 2024-04-29 00:05:42
// @Runtime: 0 ms
// @Memory: 45.7 MB
// @comment: 双指针
// @flag: WHITE
class Solution {
    public int trap(int[] height) {
        int left=0,right=height.length-1;
        int leftMax=height[left];
        int rightMax=height[right];
        int result=0;
        while(left<=right){
            if(leftMax<rightMax){
                if(leftMax>height[left]){
                    result+=leftMax-height[left];
                }else{
                    leftMax=height[left];
                }
                left++;
            }else{
                if(rightMax>height[right]){
                    result+=rightMax-height[right];
                }else{
                    rightMax=height[right];
                }
                right--;
            }
        }
        return  result;
    }
}