【算法】单调栈

思想

单调栈(Monotonic Stack)严格来说是一种数据结构，常用于求解这样的问题：在一个数组中，对每一个元素，寻找下一个比它大/小的元素。显然，它有两种：单调递增栈(Monotonic Increasing Stack)和单调递减栈(Monotonic Decreasing Stack)。

举一个单调递增栈的例子，一个数组的单调递增栈用如下方法构造：从左向右遍历数组，将新元素压栈时，判断栈顶元素是否比新元素大，如果栈顶元素更大，则弹栈，否则将新元素压栈。

对于数组：1,3,2,4,7来说，其单调栈构造过程如下：

1. 1。
2. 1,3。
3. 1,2，栈顶元素3比2大，先弹栈再将2入栈。
4. 1,2,4。
5. 1,2,4,7。

实战

本题为经典的Leetcode 42. Trapping Rain Water:

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;

        int result = 0;
        stack<int> mono_stack;

        for(int i = 0; i < height.size(); ++i){
            while(!mono_stack.empty() && height[mono_stack.top()] < height[i]){
                int top = mono_stack.top();
                mono_stack.pop();
                if(mono_stack.empty()) break;
                int length = i - mono_stack.top() - 1;
                int high = min(height[mono_stack.top()], height[i]) - height[top];
                result += length * high;
            }
            mono_stack.push(i);
        }
        
        return result;
    }
};

这道题写了蛮久，其思想基本上就是，从左向右遍历数组，维护一个单调递减栈，只要遍历到了一个比栈顶元素大的元素，就代表有可能形成一个可以装雨水的凹形容器。这时，凹形容器的右边就是当前遍历到的高度，栈顶元素表示凹形的低点，然后弹栈，接着，栈顶元素表示凹形的左侧。

举个例子：

当遍历到索引4的时候，栈顶是索引3,是凹点，所以计算的水的体积是橘色部分：

接着弹栈，栈顶是索引2，是凹点，所以计算的水的体积是黑色部分：

这样就计算出了一个不规则凹形中所能容纳雨水的体积。