题目描述

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

样例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

算法1

(双指针) $O(n)$

• 三次遍历
  1.第一次遍历：记录每个节点左边的高度最大值(如果没有就记录自己的高度)
  2.第二次遍历：记录每个节点右边的高度最大值(如果没有就记录自己的高度)
  3.第三次遍历：计算结果
• 每一根柱子所对应的水面积 = min(l[i],r[i])-height[i]

Java 代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int[] l = new int[n];
        int[] r = new int[n];
        l[0] = height[0];
        r[n-1] = height[n-1];
        int res = 0;
        for(int i = 1; i < n; i++){
            l[i] = Math.max(l[i-1],height[i]);
        }

        for(int i = n-2; i >= 0; i--){
            r[i] = Math.max(r[i+1],height[i]);
        }

        for(int i = 0; i < n; i++){
            res += Math.min(l[i],r[i])-height[i];
        }

        return res;
    }
}