85 Maximal Rectangle

85. Maximal Rectangle

1. Question

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

2. Implementation

思路：这题和Largest Rectangle Histogram的做法完全一样，唯一的不同是，那题的输入就是代表不同高度的数组，而这题需要我们根据matrix每行每个列上连续的1的个数，计算出相应的高度。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        Stack<Integer> stack = null;
        int area = 0, maxArea = 0;
        int m = matrix.length, n = matrix[0].length;

        int[] heights = new int[n + 1];

        for (int i = 0; i < m; i++) {
            stack = new Stack<>();

            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                }
                else {
                    heights[j] = 0;
                }
            }

            for (int j = 0; j <= n; j++) {
                int curHeight = j == n ? -1 : heights[j];

                while (!stack.isEmpty() && heights[stack.peek()] > curHeight) {
                    int topIndex = stack.pop();
                    area = heights[topIndex] * (stack.isEmpty() ? j : j - stack.peek() - 1);
                    maxArea = Math.max(maxArea, area);
                }
                stack.push(j);
            }
        }
        return maxArea;
    }
}

3. Time & Space Complexity

时间复杂度是O(mn), 空间复杂度O(n)