[Leetcode] Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
逐层遍历，计算一个height数组表示目前的高度值然后在这个数组上计算最大矩形的面积。计算的时候利用DP的方法来寻找某一点向左和向右所能达到的最远距离，也就是从这个最远距离到我们这个点可以形成一个递减的序列，比如说我们已经要计算i所能到达的最左距离，我们先比较i-1和i高度的大小，如果i-1不低于i，那么i-1最左能到达的地方i也能到达，设这个地方为k，那么我们继续比较k-1和i的高度，如此继续直到条件不能再满足。这一点上的面积就是(R - L + 1)*height。时间复杂度为O(n)。整体的复杂度为O(mn)。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0) return 0;
        int n = matrix[0].length;
        if(n == 0) return 0;
        int[] height = new int[n];
        for(int i = 0; i < n; i++)
            height[i] = 0;
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            result = Math.max(result, Rectangle(height));
        }
        return result;
    }
    
    private int Rectangle(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 0;
        for(int i = 1; i < n; i++) {
            int ind = i;
            while(ind > 0 && height[ind-1] >= height[i])
                ind = left[ind-1];
            left[i] = ind;
        }
        right[n-1] = n-1;
        for(int i = n-2; i >= 0; i--) {
            int ind = i;
            while(ind < n-1 && height[ind+1] >= height[i])
                ind = right[ind+1];
            right[i] = ind;
        }
        int ma = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            ma = Math.max(ma, height[i]*(right[i] - left[i] + 1));
        }
        return ma;
    }
}