题解 | #接雨水问题#

思路：

• 思路1：暴力法，找到当前点左右两个最高点left、right，然后用二者较小值减去当前值，就是当前柱子最多存储的雨水

• 思路1优化，两次遍历数组，先通过一次遍历找到每个点的左右最高点，然后再次遍历，计算当前对应柱子可以存储的雨水，降低了时间复杂度

• 思路1的优化2，无需两次遍历，因为发现左右端点高度中总有一个没有用到，若左端点小于右端点，则当前点的蓄水高度以左端点为准，反之同理

• 思路2，其实无需找到该节点的左右两个最大端点，若当前点高于前一个点，其实前一个点的蓄水量已经可以计算，就是当前点和前一个节点的再前一个节点中的较小值减去前一个节点的高度，再乘对应的宽度所以可以用非递增栈存储，注意在计算时要考虑蓄水的宽度

代码：

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here.
        //思路1的优化2，无需两次遍历，因为发现左右端点高度中总有一个没有用到，若左端点小于右端点，则当前点的蓄水高度以左端点为准，反之同理
        //所以采用双指针法
        if(arr==null||arr.length==0){
            return 0;
        }
        int left=0,right=arr.length-1;
        long res=0L;
        int leftMax=0;
        int rightMax=0;
        while(left<right){
            if(arr[left]<arr[right]){
                leftMax=Math.max(leftMax,arr[left]);
                res+=leftMax-arr[left];
                left++;
            }else{
                rightMax=Math.max(rightMax,arr[right]);
                res+=rightMax-arr[right];
                right--;
            }
        }
        
        return res;
        
        
//         //思路2，其实无需找到该节点的左右两个最大端点，若当前点高于前一个点，其实前一个点的蓄水量已经可以计算，就是当前点和前一个节点的再前一个节点中的较小值减去前一个节点的高度，再乘对应的宽度
//         //所以可以用非递增栈存储，注意在计算时要考虑蓄水的宽度
//         int res=0;
//         Deque<Integer> stack=new ArrayDeque<>();
//         for(int i=0,len=arr.length;i<len;i++){
//             while(!stack.isEmpty()&&arr[i]>arr[stack.peek()]){
//                 int temp=stack.pop();
//                 if(stack.isEmpty()){
//                     break;
//                 }
//                 int distance=i-stack.peek()-1;
//                 int border=Math.min(arr[i],arr[stack.peek()])-arr[temp];
//                 res+=distance*border;
//             }
//             stack.push(i);
//         }
        
//         return res;
        
//         //思路1优化，两次遍历数组，先通过一次遍历找到每个点的左右最高点，
//         //然后再次遍历，计算当前对应柱子可以存储的雨水，降低了时间复杂度
//         if(arr==null||arr.length==0){
//             return 0L;
//         }
//         int n=arr.length;
//         int[] left=new int[n];
//         int[] right=new int[n];
//         long res=0;
//         //初始化数组的左右端点
//         left[0]=arr[0];
//         right[n-1]=arr[n-1];
//         for(int i=1;i<n;i++){
//             left[i]=Math.max(left[i-1],arr[i]);
//             right[n-i-1]=Math.max(right[n-i],arr[n-i-1]);
//         }
//         for(int i=0;i<n;i++){
//             res+=Math.min(left[i],right[i])-arr[i];
//         }
        
//         return res;
        
//         //思路1：暴力法，找到当前点左右两个最高点left、right，然后用二者较小值减去当前值，就是当前柱子最多存储的雨水
//         int left=0;
//         int res=0;
//         for(int i=0,len=arr.length;i<len;i++){
//             left=Math.max(left,arr[i]);
//             int right=arr[i];
//             for(int j=i;j<len;j++){
//                 right=Math.max(right,arr[j]);
//             }
//             res+=Math.min(left,right)-arr[i];
//         }
//         return res;
        
    }
}