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.

分析

这题最直接的就是O(m^2 * n)的遍历（解法1），从左到右（或者从右到左）得到每个节点左（右）方连续的‘1’（包括自己）的个数。同时，从下到上（或从上到下）计算节点下方（上方）所能构成的矩形的最大值。

这题与Largest Rectangle in Histogram联系紧密，从上到下（或从下到上）得到每个节点上（下）方连续'1'（包括自己）的个数。则要得到最大矩形，就是在每一行里进行一次Largest Rectangle in Histogram，这样得到了解法2。虽然这样复杂度降到了O(m * n)，但是从LeetCode测试结果上看，解法1还更快些，可能是解法1运气好的时候剪枝比较多。

还有一种非常高大上的解法（解法3），参考http://hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba，这个是O(m * n)时间复杂度，O(n)空间复杂度。先前两种空间复杂度都是O(m * n)。

解法1

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

		// init
		int[][] dp = new int[M + 1][N + 1];

		// dp
		for (int i = M - 1; i >= 0; --i) {
			for (int j = N - 1; j >= 0; --j) {
				if (matrix[i][j] == '1') {
					dp[i][j] = dp[i][j + 1] + 1;
					int min = dp[i][j];
					int count = 1;
					int tempMax = dp[i][j];
					while (dp[i + count][j] != 0) {
						++count;
						min = Math.min(dp[i + count][j], min);
						tempMax = Math.max(min * count, tempMax);
					}
					max = Math.max(max, tempMax);
				}
			}
		}
		return max;
	}
}

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

		int M = matrix.length;
		int N = matrix[0].length;

		int max = 0;
		int[][] height = new int[M + 1][N];
		for (int i = 1; i <= M; ++i) {
			Stack
  
    stack = new Stack
   
    (); for (int j = 0; j < N; ++j) { if (matrix[i - 1][j] == '1') { height[i][j] = height[i - 1][j] + 1; } if (stack.isEmpty() || height[i][stack.peek()] <= height[i][j]) { stack.push(j); } else { int index = stack.pop(); int area = height[i][index] * (stack.isEmpty()   j : (j - stack.peek() - 1)); max = Math.max(max, area); --j; } } while (!stack.isEmpty()) { int index = stack.pop(); int area = height[i][index] * (stack.isEmpty()   N : (N - stack.peek() - 1)); max = Math.max(max, area); } } return max; } }
   
  

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

		int M = matrix.length;
		int N = matrix[0].length;
		int[] H = new int[N];
		int[] L = new int[N];
		int[] R = new int[N];
		for (int i = 0; i < N; ++i) {
			R[i] = N;
		}

		int ret = 0;
		for (int i = 0; i < M; ++i) {
			int left = 0, right = N;
			// calculate L(i, j) from left to right
			for (int j = 0; j < N; ++j) {
				if (matrix[i][j] == '1') {
					++H[j];
					L[j] = Math.max(L[j], left);
				} else {
					left = j + 1;
					H[j] = 0;
					L[j] = 0;
					R[j] = N;
				}
			}

			// calculate R(i, j) from right to left
			for (int j = N - 1; j >= 0; --j) {
				if (matrix[i][j] == '1') {
					R[j] = Math.min(R[j], right);
					ret = Math.max(ret, H[j] * (R[j] - L[j]));
				} else {
					right = j;
				}
			}
		}

		return ret;
	}
}