maximal-rectangle

题目：牛客网

解题思路：

利用递增栈，可参考https://blog.csdn.net/qq_17550379/article/details/85093224

这种解法显然很慢，我们有一种更好的思路就是通过递增栈。所谓的递增栈，就是栈中只存放递增序列。

我们首先将2加入到栈中，我们接着访问1，我们发现1比栈顶元素2小，所以我们将栈顶元素2弹出，并且记录此时的面积2。我们发现栈已经空了，所以我们要接着压栈。

接着我们通过不断遍历找到第二个递增栈。

我们接着访问2，我们发现此时2比栈顶元素6小，所以我们弹出栈顶元素6，并且记录此时的面积6*1=6。

此时栈中还有元素，我们发现此时2依旧比栈顶元素5小，所以我们需要将栈顶元素5弹出，并且我们记录此时出栈元素构成的最大面积5*2=10。

我们发现此时的2比栈顶元素大了，我们就将2压入栈中，接着将3压入栈中。此时遍历结束，我们发现栈不为空，所以我们需要进行出栈操作，出栈的同时记录出栈元素构成的最大面积即可。

import java.util.Stack;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        //若矩阵为null，或长度为0，或宽度为0，则直接返回0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int max = 0;
        int[] h = new int[col];
        for (int i = 0; i < row; i++) {
            Stack<Integer> stack = new Stack<Integer>();
            stack.push(-1);
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1')
                    h[j] += 1;
                else
                    h[j] = 0;
 
            }
            for (int j = 0; j < col; j++) {
                while (stack.peek() != -1 && h[j] < h[stack.peek()]) {
                    int top = stack.pop();
                    max = Math.max(max, (j - 1 - stack.peek()) * h[top]);
                }
                stack.push(j);
            }
            while (stack.peek() != -1) {
                int top = stack.pop();
                max = Math.max(max, (col - 1 - stack.peek()) * h[top]);
            }
        }
        return max;
    }
}