通过使用堆栈这一简单的结构，可以巧妙地降低一些问题的时间复杂性。
单调堆栈的性质：
1、单调递增堆栈时，堆栈从顶部到底部的元素会严格增加。 对于单调递减堆栈，从堆栈顶部到底部的元素会严格减少。
2、离堆栈顶部越近的要素越向后进入堆栈。 (很明显) )。
本文介绍单调堆栈的使用方法
通过一个问题来说明。
POJ2559
1. 题目大意：链接
给出圆柱形统计图(histogram )，其各项宽为1，高度与具体问题有关。 现在，程序求出这个条形图中最大面积的长方形。
() (4)5)3) 7所示的条形图分别有2(1)4)5)1)3) 7个数据。 对应的条形图如下所示，最后求出的面积最大的图表如右图所示。
做法1 :列举各起点和终点，矩形面积为长*最小高度。 o(n^3) ) ) )。
方法2 :区间最小值优化。 o (n (2) ) ) )。
做法3 :以各下标为中心向两侧扩展，遇到更短的就停下来。 这样，就可以确定各下标高度最高的矩形。 o (n (2) ) ) )。
单调递增堆栈：保持单调递增堆栈，所有元素一次进入堆栈，只需退出堆栈。 在每个元素离开堆栈时更新最大的矩形面积。
流程：
1 )判断当前要素小于堆栈顶部
2 )如果满足条件，则可以更新堆栈顶部元素的最大长度，并弹出堆栈顶部
3 )继续运行1 )，直到不再满足条件。
重要结论：
1）栈顶下面一个元素一定是，栈顶左边第一个比栈顶小的元素
2）当前元素一定是，右边第一个比栈顶小的元素。
为什么呢？
例如，这是一个堆栈
，
1 )如果右边存在距离更近的比1号小的数，一天早就跑出去了。
2 )如果左边有距离更近的比1号小的数
如果那个小于2号，就跳出2号，自己成为2号
如果那个比2号大的话，2号不会飞出，但是堆栈变成2号，原来的2号变成3号。
所以不管怎么说，这个逻辑是正确的。
最后加入代码进行说明
让我们来看看难题
leet代码85 maximal rectangle
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6，三行后面的六个1
给出由二进制组成的矩阵map，找到只包含1的最大矩形，并返回其面积。
这个问题一行一行地做着。 每一行求出与各要素对应的高度。 这个高度是对应的连续的1的长度。 然后按每行更新最大矩形面积。
1连续的长度也经常更新。 此元素为0，长度为0。 这个要素是1，再加上前面的东西。
用具体想法的代码说明。
import java.util.Stack； publicclassmaximalrectangle { publicstaticintmaxrecsize (int [ ] map ) if (map==null|| map.length==0| map () ) int [ ] height=new int [ map [0].length ]； for(intI=0； i map.length； I ) for(intj=0； j map[0].length； j({Height[j]=map[I][j]==0？ 0 : height[j] 1； //0的长度为0，1的长度为前面的1 } Maxarea=math.max (maxrecfrombottom (height )、maxarea )； //调用第一个问题的思想(}返回矩阵； (/第一题构想publicstaticintmaxrecfrombottom (int [ ] height ) if ) height==null|||height.length==0) {return 0； (}int maxArea=0； stackintegerstack=newstackinteger (； for(intI=0； i height.length； I () /堆栈不为空且堆栈顶部较大的while (！ stack.isempty (height [ I ]=height [ stack.peek ] ) (](intj=stack.pop )； 弹出int k=stack.isEmpty (？ -1 : stack.peek (； intcurarea=(I-k-1 ) * height[j]； //计算最大maxarea=math.max(maxarea，curArea )； //更新总体最大(stack.push ) I； //推入新元素直到堆栈顶部变小}//最后一个堆栈不为空，右侧没有更小的元素，while (！ stack.isEmpty () ({int j=stack.pop )； int k=stack.isEmpty (？ -1 : stack.peek (； intcurarea=(height.length-k-1 ) * height[j]； Maxarea=math.max(Maxarea，curArea )； }返回矩阵； } publicstaticvoidmain (string [ ] args ) int[] ) map={ 1，0，1，1 }，{ 1，1，1，1 }，{ 1，1 } }