面积最大的矩形

题目描述：
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例：
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

Java代码：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for(int row = 0;row < matrix.length;row++) {
            for(int col = 0;col < matrix[0].length;col++) {
                if(matrix[row][col] == '1') heights[col] += 1;
                else heights[col] = 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len == 0) return 0;
        if(len == 1) return heights[0];
        int res = 0;

        int[] new_heights = new int[len + 2];
        new_heights[0] = 0;
        System.arraycopy(heights, 0, new_heights, 1, len);
        new_heights[len + 1] = 0;
        len += 2;
        heights = new_heights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        stack.add(0);

        for(int i = 0;i < len;i++) {
            while(heights[i] < heights[stack.peekLast()]) {
                int cur_height = heights[stack.pollLast()];
                int cur_width = i - stack.peekLast() - 1;
                res = Math.max(res, cur_height * cur_width);
            }
            stack.add(i);
        }

        return res;
    }
}