Maximal Rectangle @LeetCode

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

A little harder than Largest Rectangle in Histogram.

	package leetcode.array;
	import java.util.Stack;
	/**
	* Solution: 切割每行， 然后对每行，做 largest rectangle in Histogram 类似的操作, 可以看做current line 时候，current 和上面所有行的直方图
	* 唯一区别是height[] 这里的优化，每次新的一行，为0, 说明断开了，则当前height[j] = 0, 如果为1， 则height[]
	*
	* 我们如何计算某一行为底面时直方图的高度呢？ 如果重新计算，那么每次需要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹，
	* 如果我们知道上一行直方图的高度，我们只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。
	* 利用历史信息，我们就可以在线行时间内完成对高度的更新。我们知道，Largest Rectangle in Histogram的算法复杂度是O(n)。
	* 所以完成对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次，那么算法总时间复杂度是O(m*n)。
	* 空间上，我们只需要保存上一行直方图的高度O(n)，加上Largest Rectangle in Histogram中所使用的空间O(n)，所以总空间复杂度还是O(n)
	*
	* Reference: http://codeganker.blogspot.com/2014/04/maximal-rectangle-leetcode.html
	* @author jeffwan
	* @date May 18, 2014
	*/
	public class MaximalRectangle {
	public int maximalRectangle(char[][] matrix) {
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return 0;
	}
	int m = matrix.length;
	int n = matrix[0].length;
	int max = 0;
	int[] height = new int[n];
	for (int i = 0; i < m ; i++) {
	for (int j = 0; j < n; j++) {
	height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
	}
	max = Math.max(max, maximalRectangleHelper(height));
	}
	return max;
	}
	private int maximalRectangleHelper(int[] height) {
	int max = 0;
	Stack<Integer> stack = new Stack<Integer>();
	for (int i = 0; i <= height.length; i++) {
	int current = (i == height.length) ? -1 : height[i];
	while (!stack.isEmpty() && current <= height[stack.peek()]) {
	int h = height[stack.pop()];
	int w = stack.isEmpty() ? i : i - stack.peek() - 1;
	max = Math.max(max, h * w);
	}
	stack.push(i);
	}
	return max;
	}
	}

view raw MaximalRectangle.java hosted with ❤ by GitHub