单调栈的定义是指一个栈，其中从栈顶往栈底看，其中所有的元素都是只有一个单调的关系。而其中又包括严格单调栈以及非严格单调栈

单调栈的入栈

单调栈的入栈需要持续检查栈顶的元素。以单调递增（从栈底到栈顶的元素依次递增的栈为例）如果栈顶元素比即将入栈的元素小的时候，就应该执行出栈操作，直到栈顶元素大于入栈元素，再进行入栈操作。例如对于已经存在的栈：5，4，2，1，当需要入栈3的时候，就应该把1和2都出栈，然后再把3入栈。入栈之后的栈中元素应该有5，4，3。

相关题目（待补充）：

LeetCode 84 Largest Rectangle in Histogram

这个题目要求是给定一定数量的矩形，要求由这些矩形围成的面积最大的矩形的面积，样例如下图：

这道题中有一个特点，对于能形成一个大矩形的不同条形，需要满足矩形中包括的所有条的值应该至少要大于其中最小的矩形。如上图中下标为1，2，3的三个条形实际上可以连为高为1的矩形，而下标为0，1，2，3明显不能连起来形成高为2的矩形。

考虑到题目的特点，我们可以维护一个单调栈。首先让单调栈有一个默认的栈底-1，代表整个图中的最低处（默认为0，实际上是方便处理）。单调栈中储存条形的下标。其中每一个下标实际上都表示当前下标到前一个下标这一个区间范围内的条形高的最小值。

当要计算以某一个高度为最低点的矩形的时候，其中有两个部分需要计算，其中一个部分是该点左边的部分，另外一部分则是该点右边的部分。对于上图的入栈过程，不难得到当某一个时刻，其中单调栈中会有储存[-1,1,4,5]的情况，这个时候对应的条形的高度就分别是[0,1,2,3]。其中，(1,4]中的最小值就是2。当计算以下标4为最低点（即高为2的矩形）的时候，左边的部分的值就是[2,4]的区间长度再乘2。

而另一部分需要计算的则是一个点后面不比其低的部分。实际上当4后面坐标的数仍然能够在4的上面被压入栈中的话，由单调栈的特性，当4没有从栈中被弹出的时候，后面的数都会不小于2。因此实际上需要计算的则是当一个数从栈中被弹出的时候，新的元素下标到当前元素下标的距离。例如当栈中元素为[1,2,3]的时候（对应元素为[1,5,6]），当下一个下标4的元素值为2，当5即将被2弹出的时候，其需要计算的宽度就是(2,4)的宽度，即(4-2+1)=1了（为了避免和上一个部分重复）。

通过以上的两个部分，就能够通过对于单调栈的不断压栈的处理，就能完成矩形最大面积的计算了。由于在循环中，每一个元素最多被压栈以及出栈1次，因此时间复杂度为O(n)，空间复杂度与栈相关，最坏情况是所有元素都被压栈，因此空间复杂度也为O(n)。

代码如下（我的）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> monotonicStack;
        int minHeight;
        int r = 0;
        monotonicStack.push(-1);
        for (int i=0; i<heights.size(); i++) {
            if (monotonicStack.top() == -1 || heights[i]>=heights[monotonicStack.top()]) {
                monotonicStack.push(i);
            } else {
                while (monotonicStack.top()!=-1 && heights[monotonicStack.top()] > heights[i]) {
                    int k = monotonicStack.top();
                    monotonicStack.pop();
                    r = max(r,(i-1-monotonicStack.top())*heights[k]);
                }
                monotonicStack.push(i);
            }
        }
        int n=heights.size();
        while (monotonicStack.top()!=-1 && monotonicStack.size()>0) {
            int k = monotonicStack.top();
            monotonicStack.pop();
            r = max(r,(n-1-monotonicStack.top())*heights[k]);
        }
        return r;
    }
};

LeetCode 85. Maximal Rectangle

实际上可以通过转换变为与84一样的题目，只是对于矩阵的每一列或者每一行都做一遍84题中的求最大矩形的过程即可。每一行求一次时间复杂度O(n)，一共m行则时间复杂度为O(mn)。空间复杂度可以做到O(m)，下一行的高度由上一行的高度以及原矩阵在当前位置上的值决定即可。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> heights(n);
        int _max=0;
        for (int i = 0; i < n; i++) {   //row 0
            heights[i] = matrix[0][i] - 48;
        }
        int r = largestRectangleArea(heights);
        _max = max(_max,r);
        for (int i=1; i<m; i++) {   //row 1 to n-1
            for (int j=0; j<n; j++) {
                if (matrix[i][j] == '0') {
                    heights[j] = 0;
                } else {
                    heights[j] = heights[j]+1;
                }
            }
            int r = largestRectangleArea(heights);
            _max = max(_max,r);
        }
        return _max;
    }
    //largestRectangleArea函数与84一致
};

LeetCode 2281