思路:

• 分析题意发现
• 每次新进来一个柱子，如果它比左边的柱子高的话就会产生新的水池
• 而要计算它进来产生的水池就要找到左边第一个比它高的柱子
• 找左边第一个比它高的柱子就要用到单调栈
• 在更新单调栈的过程中更新答案
• 令t=当前栈顶元素，last=上一个出栈元素的高度
• 通过画图来分析计算面积的过程
• area += (i - t - 1) * (height[t] - last)

/**
每次新进来一根柱子
*/
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] stk = new int[n+10];
        int tt = 0;
        int ans = 0;
        for(int i = 0 ; i < n ;i++){
            //last代表上一个出栈元素的高度
            int last = 0;
            while(tt != 0 && height[stk[tt]] <= height[i]){
                //当要进来的元素高度大于栈顶元素，出栈,更新结果
                //保证整个栈是单调递减的
                //t代表当前栈顶元素的高度
                int t = stk[tt--];
                ans += (i - t - 1) * (height[t] - last);
                last = height[t];
            }
            //如果更新完后栈还不为空，即目前栈顶元素高度大于height[i]
            if(tt != 0)
                ans += (i - stk[tt] - 1) * (height[i] - last);
            stk[++tt] = i;
        }
        return ans;
    }
}