单调栈

leetcode - 42. 接雨水
单调栈即元素严格单调递增或单调递减的栈，只需要在元素入栈的时候保持栈的单调性即可(新元素入栈前先把栈中所有比它小的元素弹出)。
对于leetcode第42题，把每一根柱子作为栈元素，形成一个递减的单调栈，即可解决问题。
代码如下，详细解释见注释：

class Solution {  // 单调栈
    public int trap(int[] heights) {
        int h, w, idx, result = 0;
        Element e = null, top1 = null, top2 = null;
        Stack<Element> stack = new Stack<>();

        // 跳过开头所有高度为0的元素，找到第一个非0元素
        for (idx = 0; idx < heights.length; ++idx) {
            if (heights[idx] != 0) break;
        }

        for (; idx < heights.length; ++idx) {
            e = new Element(idx, heights[idx]);  // 新元素

            if (stack.empty()) {
                stack.push(e);
            } else {
                top1 = stack.peek();
                if (top1.val < e.val) {  // 新柱子比栈顶高
                    // 注意出栈时栈里至少要留出一根柱子，否则水就从左边溜走了
                    while (stack.size() > 1 && top1.val < e.val) {
                        stack.pop();
                        top2 = stack.peek();

                        // 高度（top1是底，top2和e是左右两个边）
                        h = Math.min(e.val, top2.val) - top1.val;

                        // 宽度
                        w = e.idx - top2.idx - 1;

                        // 求面积
                        result += h * w;
                        top1 = top2;
                    }

                    if (stack.size() == 1 && top1.val < e.val) {
                        // 如果栈中的最后一个柱子比e矮，直接丢弃
                        stack.pop();
                    }

                    // 新柱子入栈
                    stack.push(e);
                } else if (top1.val == e.val) {
                    // 遇到高度相同的柱子，只需要更新栈顶元素的下标即可
                    // 因为栈里的元素只能作为左侧的边或者底部
                    // 当它作为底时，它的下标不影响计算
                    // 当它作为左侧边时，对于高度一样的柱子，需要选最右的柱子
                    top1.idx = e.idx;
                } else {
                    // 比栈顶元素小，直接入栈
                    stack.push(e);
                }
            }
        }

        return result;
    }
}

class Element {
    // 保存每个柱子的下标和高度
    int idx, val;
    public Element(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}

参考：
[1]. https://zhuanlan.zhihu.com/p/26465701