单调栈–柱状图中最大的矩形84

单调栈的作用就是维护一个单调递增或者单调递减的栈（但里面存的是下标，因为这样才好得到位置关系），有点类似于一个滑动窗口的单调队列，但队列是后来先出，而栈可以保留最初的哪个值到最后。
操作就是如果是递减，则此时元素小于栈顶元素，则入栈。若大于等于，则pop直到栈顶元素比它大，再入栈。通常为了免去判断栈为空，会根据单调性设置两个哨兵节点来使得栈中永不为空。想这种题的时候要从每一个节点来入手。
选出中间连着的最大的数组内部的矩形，所以每个点都可以作为这个矩形的最左端，遍历数组，以这个点作为最左端要求它的最右端不能低于这个点的值。
所以可以想到用一个单调栈来维护这个矩形，将此点加入单调栈后，一直往右遍历，如果遇到大于等于它的数则加入栈中。如果遇到小于它的数，则这个矩形是完成了，所以计算这一段所有点的面积，就是栈的长度（i-s.pop）乘一开始的那个值arr[s.pop]。然后一直pop到比这个数小的数出现。

public class Solution {

    public int largestRectangleArea(int[] heights) {
         int[] num=new int[heights.length+2];
        num[0]=0;
        for(int i=1;i<=heights.length;i++){
            num[i]=heights[i-1];
        }
        num[num.length-1]=0;
        Deque<Integer> s=new LinkedList<Integer>();
        s.push(0);
        int res=0;
        for(int i=1;i<num.length;i++){
            while(num[i]<num[s.peek()]){
                int len=num[s.pop()];
                res=Math.max(len*(i-s.peek()-1),res);
            }
            s.push(i);
        }
        return res;
    }
}