题目

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

思考

建立一个栈，栈为空时，如果数大于0就push，并且保存第一个数，遍历，如果小于第一个数的就push，大于的话就开始pop，循环完成后可能会遇到栈底的数最大，栈不为空，就还需要进行一个循环，反过来计算直到栈为空

代码

import java.util.Stack;

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int min = 0;
        for (int x : height) {
            if (stack.isEmpty() && x > 0) {
                stack.push(x);
                min = x;
            } else if (!stack.isEmpty() && x < min) {
                stack.push(x);
            } else if (!stack.isEmpty() && x >= min) {
                while (!stack.isEmpty()) {
                    if (min - stack.peek() > 0)
                        count += min - stack.pop();
                    else
                        stack.pop();
                }
                stack.push(x);
                min = x;
            }
        }
        int max = 0;
        while (!stack.isEmpty()) {
            if (max == 0) {
                max = stack.pop();
            } else if (max <= stack.peek()) {
                max = stack.pop();
            } else {
                count += max - stack.pop();
            }
        }
        return count;
    }
}