Maximum Rectangle

https://leetcode.com/problems/maximal-rectangle/description/

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.

Thoughts

找全局的max rectangle等价于max_i对每一层找最大的rectangle. 那么对于一行来说, 它的max rectangle备选有谁呢? 分别是每一列j, 由它当前高度(前面行当前列到该列累计1的个数)往左右两边扩, 能最远扩到哪. 因此这道题可以转化成:

让height(i, j)表示(i, j)处高度(累计1的个数), left(i, j)表示以height(i, j)为高往左走最远能到的坐标, right(i, j)为对应右的.

求maxi,j([right(i, j) - left(i, j)] * height[i, j]).

height[i,j]可以轻易通过height[i - 1, j] + 1得到. left(i, j)我们可以分类讨论下, 当(i, j)是1时, 它相当于是从上一层延续下来, 最远也就能和left(i - 1, j)相同, 但如果本层左边在left(i - 1,j)的右边的curLeft - 1处出现了0, 那么最远也就能拓到curLeft处. right同理.

Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length, n = m == 0 ? 0 : matrix[0].length;
        if (m == 0 || n == 0) {
            return 0;
        }

        int[] height = new int[n];
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        int res = 0;
        for (int i = 0; i < m; i++) {
            int curLeft = 0, curRight = n;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j] += 1;
                } else {
                    height[j] = 0;
                }
            }

            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = Math.max(left[j], curLeft);
                } else {
                    curLeft = j + 1;
                    left[j] = 0;
                }
            }

            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], curRight);
                } else {
                    curRight = j;
                    right[j] = n;
                }
            }
            for (int j = 0; j < n; j++) {
                res = Math.max(res, (right[j] - left[j]) * height[j]);
            }
        }

        return res;
    }
}