题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

题解

• 能存水的前提是，左右两边的高度都要大于0。而水位的高度则取决于矮的一边，和木桶存水一样。
  我们可以用两个int记录左右两边的已知最高高度。随着指针的移动，最高高度也会更新。
• 每一格的存水量，取决于当前块和下一块的高度差。
  

class Solution {
   
    public int trap(int[] height) {
   
        if(height==null||height.length==0){
   
            return 0;
        }
        int left = 0;
        int right = height.length-1;
        int sum = 0;
        int leftHeight = height[left];
        int rightHeight = height[right];
        while(left<right){
   
            if(leftHeight<=rightHeight){
   
                if(leftHeight>height[left+1]){
   
                    sum+=leftHeight-height[left+1];
                }else{
   
                    leftHeight = height[left+1];
                }
                left++;
            }else{
   
                if(rightHeight>height[right-1]){
   
                    sum+=rightHeight-height[right-1];
                }else{
   
                    rightHeight = height[right-1];
                }
                right--;
            }
        }
        return sum;
    }
}