单调栈--最大矩形85

和最大正方形锤子关系没有，人家可以通过动态规划来求，但这个不能，这个是把二维数组看成是一维数组，上面的值当成这个点处的高度。就可以类比于柱状图中的最大矩形，用单调栈来求。重点是怎么把它转换为一个柱状图。答案是一行一行求。从最上面一行求这个数组，如果此时值为1，则把它加进去，如果不是1，则它就断了，让这个点处为0.变焦一个最大的即可。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows=matrix.length;if(rows==0)return 0; 
        int cols=matrix[0].length;
        int[] height=new int[cols];
        int res=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if (matrix[i][j] == '1') {
                height[j] += 1;
            } else {
                height[j] = 0;
            }
            }
            res=Math.max(core(height),res);
        }
        return res;
    }
    public int core(int[] height){
        int[] num=new int[height.length+2];
        num[0]=0;
        for(int i=1;i<=height.length;i++){
            num[i]=height[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;
    }
}