题目描述

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

样例

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。

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

算法分析

单调栈
按照每个柱形的横向方向计算

• 1、枚举每一个柱形，按照横向扩展面积，找到左侧第一个比它大的数，找到右侧第一个比它大的数，则该柱形对应的面积为$S=【min(h[left[i]],h[right[i]])−柱形的高度】∗(right−left−1)$
• 2、使用单调栈找出所有位置左边离它最近的比它大的柱形对应的位置left[]以及出所有位置右边离它最近的比它大的柱形对应的位置right[]
• 3、维护单调递减栈的方法：从左到右，将新进来的元素与栈顶元素进行判断，若栈顶元素比新进的元素小，则pop出栈顶元素，最终保证栈顶元素一定是单调递减栈中元素最小，且比新进来的元素大，则找到该位置左边离它最近且比它大的数，从右到左边同理。
• 4、注意：若遇到同等高度且扩展的是同一个区域面积时候，默认左边的同等高度是离它最近比它大的高度，右边不默认

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int trap(int[] h) {
        int n = h.length;
        int[] left = new int[n + 10];
        int[] right = new int[n + 10];
        int tt = 0;
        int[] stk = new int[n + 10];

        //找到左边第一个比它大的元素
        for(int i = 0;i < n;i ++)
        {
            while(tt != 0 && h[stk[tt]] <= h[i]) tt --;
            if(tt == 0) left[i] = -1;
            else left[i] = stk[tt];
            stk[++ tt] = i;
        }
        tt = 0;
        //找到右边第一个比它大的元素
        for(int i = n - 1;i >= 0;i --)
        {
            while(tt != 0 && h[stk[tt]] < h[i]) tt --;
            if(tt == 0) right[i] = n;
            else right[i] = stk[tt];
            stk[++ tt] = i;
        }
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            if(right[i] == n || left[i] == -1) continue;
            int len = right[i] - left[i] - 1;
            res += (Math.min(h[left[i]],h[right[i]]) - h[i]) * len;
        }
        return res;
    }
}