image.png

解法

暴力

直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
算法
image.png

  1.     public int trap(int[] height) {
  2.         int ans = 0;
  3.         int size = height.length;
  4.         for(int i=1;i<size-1;i++){
  5.             int maxLeft = 0,maxRight=0;
  6.             for(int j=i;j>=0;j--)
  7.                 maxLeft=Math.max(height[j], maxLeft);
  8.             for(int j=i;j<size;j++)
  9.                 maxRight=Math.max(height[j], maxRight);
  10.             ans+=Math.min(maxLeft,maxRight)-height[i];
  11.         }
  12.         return ans;
  13.     }

复杂性分析

  • 时间复杂度： O(n^2)。数组中的每个元素都需要向左向右扫描。
  • 空间复杂度 O(1) 的额外空间。

    双指针法

    image.png
public int trap(int[] height) {
        int ans = 0;
        int left=0,right=height.length-1;
        int leftMax =0,rightMax=0;
        //双指针
        while(left<right){
            //取高度的最小值进行更新
            if(height[left]<height[right]){
                if(height[left]>=leftMax)       //更新最值
                    leftMax=height[left];
                else
                    ans+=leftMax-height[left];  //更新结果
                left++;
            }else{
                if(height[right]>=rightMax)
                    rightMax=height[right];
                else
                    ans+=rightMax-height[right];
                right--;
            }
        }
        return ans;
    }
}

复杂性分析

  • 时间复杂度： O(n)
  • 空间复杂度 O(1) 的额外空间。