[LeetCode]Maximal Rectangle

这道题要用到Maximum Rectangle in Histogram的解法，本质上这一题每一层就是一个histogram，所以我们维护一个数组，从上向下扫每一层更新一下histogram的高度，然后再找maximum rectangle in histogram，最后返回最大的就可以。假设我们输入的char board[i][j]，f[j]代表当前层j位置直方的高度，DP方程是

• if board[i][j] == '0', f[j] = 0;
• else, f[j] = f[j] + 1;

假设输入数组有m列，n行，总的时间复杂度是O(m * n)，空间复杂度是O(n)，代码如下：

	public class Solution {
	public int maximalRectangle(char[][] matrix) {
	if (matrix == null)
	return 0;
	int rows = matrix.length;
	if (rows == 0)
	return 0;
	int cols = matrix[0].length;
	int[] arr = new int[cols];
	int max = 0;
	for (int i = 0; i < rows; i++) {
	for (int j = 0; j < cols; j++)
	arr[j] = matrix[i][j] == '0'? 0: arr[j] + 1;
	int area = getArea(arr);
	max = area > max? area: max;
	}
	return max;
	}
	private int getArea(int[] hist) {
	int len = hist.length;
	Stack<Integer> stack = new Stack<Integer>();
	int max = 0;
	for (int i = 0; i <= len; i++) {
	int curr = i == len? 0: hist[i];
	while (!stack.isEmpty() && hist[stack.peek()] >= curr) {
	int height = hist[stack.pop()];
	int width = stack.isEmpty()? i: (i - stack.peek() - 1);
	int area = height * width;
	max = area > max? area: max;
	}
	stack.push(i);
	}
	return max;
	}
	}

view raw maximal rectangle.java hosted with ❤ by GitHub

另外更General的解法也是用DP，对于每一个为1的点，我们要维护三个变量，也就是其左右边界left，right和高度height，我们可以在每一行每一行遍历的过程中更新这些值。假如我们是从上到下遍历的话：

• height[i]维护的是当前行第i个元素上面有多少个连续的1，包括自己
• left[i]维护的是当前元素所在的高度为height[i]的矩形的左边界
• right[i]维护的是当前元素所在的高度为height[i]的矩形的右边界

因此从第0行开始到当前行为止，对于每一个不同高度的矩形，在知道左右边界的情况下，我们可以算出面积最大值，那么遍历完所有行的话，在知道每一个高度对应的最大矩形的情况下，我们可以找出面积最大的矩形。我们用left[i]，right[i]和height[i]来表示当前行第i列的元素其所在的最大rectangle的最右边界和高度，那么我们有递归公式：

• 如果当前为1
• left[i] = max(left[i], currLeft)，currLeft为当前元素在当前行的连续的1的左边界
• right[i] = min(right[i], currRight, 同理
• height[i] = height[i] + 1
• 如果为0
• left[i] = 0，更新currLeft
• right[i] = n - 1，更新currRight
• height[i] = 0

我们不断更新rectangle的最大面积即可。每一行我们只需要左右各扫一次，时间按复杂度还是O(m * n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int maximalRectangle(vector<vector<char>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, res = 0;
	//dp[0] left, dp[1] right, dp[2] height
	vector<vector<int>> dp(3, vector<int>(n, 0));
	fill_n(dp[1].begin(), n, n - 1);
	for(int i = 0; i < m; ++i)
	{
	int currLeft = 0, currRight = n - 1;
	//left and height
	for(int j = 0; j < n; ++j)
	{
	if(matrix[i][j] == '1')
	{
	dp[0][j] = max(currLeft, dp[0][j]);
	++dp[2][j];
	}
	else
	{
	dp[0][j] = 0;
	dp[2][j] = 0;
	currLeft = j + 1;
	}
	}
	//right and area
	for(int j = n - 1; j >= 0; --j)
	{
	if(matrix[i][j] == '1')
	{
	dp[1][j] = min(currRight, dp[1][j]);
	int area = (dp[1][j] - dp[0][j] + 1) * dp[2][j];
	res = max(area, res);
	}
	else
	{
	dp[1][j] = n - 1;
	currRight = j - 1;
	}
	}
	}
	return res;
	}
	};

view raw Maximal Rectangle.cpp hosted with ❤ by GitHub