博文中会简要介绍Leetcode P0085题目分析及解题思路。
“Maximal Rectangle”是一道经典难题，也可以算作p0084的衍生题。这道题同样有两种主要解法，一种是利用动态规划，另一种是同时利用动态规划和单调栈。
Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
首先介绍动态规划的解法。这道题的动态规划思路很巧妙，我们可以先来观察如下网格，
给定如下网格，
c
1 0 1 1 1
1 0 1 1 1
r 1 1 1 1 1
1 0 0 1 0
我们不难得到这个网格中由1构成的最大矩形的面积是9，这个最大矩形的右下角是grid[r][c]，并且长宽分别是3和3。再观察下述网格，
c
1 0 1 0 0
1 0 0 1 1
1 0 1 1 1
0 0 0 1 1
r 1 1 1 1 1
不难得到这个网格中由1构成的最大矩形的面积是8，这个最大矩形的右下角是grid[r][c]，并且长宽分别是2和4。
根据上述两个例子，我们可以思考在网格中决定了由1构成的矩形的最大面积是什么。当我们知道以grid[r][c]为终点的由1构成的水平边长为W时，我们想知道的是潜在的竖直边长H，这样一来我们可以通过W*H求出矩形面积。
我们可以从第r-1行看到第0行，如果从第r-1行到第k行，每一行以grid[k][c]为终点的由1构成的水平边长都大于等于W时，我们可以知道H=r-k+1，譬如上述第一个例子。
如果从第r-1行看到第0行，若grid[k][c]为终点的由1构成的的水平边长小于W时，根据木桶短板效应，此时的水平边长W会被约束为grid[k][c]能构成的水平边长，就譬如上述第二个例子。
综上可知，当不存在更短水平边长时，矩形面积等于W*H；当存在更短水平边长W’时，矩形面积等于W‘*H。
根据上述观察，我们不难得到递推式，
令dp[r][c]是以grid[r][c]为右边界的由1构成的水平最大边长，
矩形最大面积maxRect存在下列等式
maxRect = max{ rect[r][c] }
而rect[r][c]则由下述等式得到，
width = min(width, dp[k][c]),
rect[r][c] = max{ width*(r-k+1)) }, 0<=k<=r
根据上述递推式我们可以得到动态规划的解法。
以下是Java的题解代码实现。
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0)
return 0;
int H = matrix.length, W = matrix[0].length, maxArea = 0;
int[][] dp = new int[H][W];
// DP
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (matrix[r][c] == '1') {
dp[r][c] = (c > 0)? dp[r][c-1]+1: 1;
int width = dp[r][c];
for (int itr=r; itr>=0; --itr) {
width = Math.min(dp[itr][c], width);
maxArea = Math.max(maxArea, width*(r-itr+1));
}
}
}
}
return maxArea;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty())
return 0;
int max_area = 0;
int height = matrix.size(), width = matrix[0].size();
vector<vector<int>> dp(height, vector<int>(width, 0));
// Dynamic Programming
for (int idx1=0; idx1<height; ++idx1) {
for (int idx2=0; idx2<width; ++idx2) {
if (matrix[idx1][idx2] == '1') {
// Compute the maximum width and update dp with it
dp[idx1][idx2] = (idx2 == 0)? 1: dp[idx1][idx2-1]+1;
int cur_width = dp[idx1][idx2];
// Compute the maximum area rectangle with a lower right corner at [idx1, idx2]
for (int idx3=idx1; idx3>=0; --idx3) {
cur_width = min(cur_width, dp[idx3][idx2]);
max_area = max(max_area, cur_width*(idx1-idx3+1));
}
}
}
}
return max_area;
}
};
第二种解法则是利用了p0084的单调栈思想，将本题转换为在直方图上求最大矩形面积，即p0084。我们只需要维护一个一维数组，用于记录以当前第r行为底的直方图形状即可（所谓形状，就是记录每个位置的直方形高度）。然后将这个一维数组当作直方图输入到p0084的单调栈解法里即可得到以当前第r行为底的最大矩形面积，然后遍历每一行就可以得到整个网格中的最大矩形面积。
以下是第二种解法的Java题解代码实现，利用了动态规划和单调栈。
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0)
return 0;
int maxRect = 0, H = matrix.length, W = matrix[0].length;
int[] dp = new int[W];
// Dynamic Programming + Using Stack
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
// Update the state of this row's histogram using the last row's histogram
// By keeping track of the number of consecutive ones
dp[c] = (matrix[r][c] == '1')? dp[c]+1: 0;
}
// Update maxRect with the maximum area from this row's histogram
maxRect = Math.max(maxRect, this.largestRectangleArea(dp));
}
return maxRect;
}
private int largestRectangleArea(int[] heights) {
int N = heights.length;
if (N == 0)
return 0;
Deque<Integer> stack = new LinkedList<>();
int maxRect = 0, top = -1, rect = 0;
stack.offerFirst(-1);
for (int itr=0; itr<N; ++itr) {
top = stack.peekFirst();
while ((top = stack.peekFirst()) != -1 && heights[top] >= heights[itr]) {
top = stack.pollFirst();
rect = (itr-stack.peekFirst()-1)*heights[top];
maxRect = Math.max(maxRect, rect);
}
stack.offerFirst(itr);
}
while (stack.size() > 1) {
top = stack.pollFirst();
rect = (N-stack.peekFirst()-1)*heights[top];
maxRect = Math.max(maxRect, rect);
}
return maxRect;
}
}
以下是第二种解法的C++题解代码实现，利用了动态规划和单调栈。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty())
return 0;
int max_area = 0, height = matrix.size(), width = matrix[0].size();
vector<int> dp(matrix[0].size());
// Dynamic Programming + Using Stack
for (int idx1=0; idx1<height; ++idx1) {
for (int idx2=0; idx2<width; ++idx2) {
// Update the state of this row's histogram using the last row's histogram
// By keeping track of the number of consecutive ones
dp[idx2] = (matrix[idx1][idx2] == '1')? dp[idx2]+1: 0;
}
// Update max_area with the maximum area from this row's histogram
max_area = max(max_area, this->_LargestRectangleArea(dp));
}
return max_area;
}
private:
int _LargestRectangleArea(vector<int>& heights) {
if (heights.empty())
return 0;
// Using stack
stack<int> left;
left.push(-1);
int right = 0, max_area = 0, len = heights.size();
while (right < len) {
while (left.top() != -1 && heights[right] < heights[left.top()]) {
int cur_idx = left.top();
left.pop();
max_area = max(max_area, heights[cur_idx]*(right-1-left.top()));
}
left.push(right);
++right;
}
while (left.top() != -1) {
int cur_idx = left.top();
left.pop();
max_area = max(max_area, heights[cur_idx]*(len-1-left.top()));
}
return max_area;
}
};