题目
Maximal Rectangle
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:
Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6
分析
这道题的意思很明确,给出一个二维矩阵,让我们从中找出由1组成的最大矩形面积,和上周那题一样,都是要求最大矩形面积,但输入由一维数组变成了二维数组。
解法一
如果采用暴力求解的话,我们可以先找出所有只由1组成的矩形(一个个遍历元素,从它开始向右、向下再向右扩展),再从中计算出最大的矩形面积。但用暴力求解来解上周那一维输入的题运行时间都超了1000ms,这次肯定会超时,因此我没有采用这种解法。
实际上,这两道题之间有着很大的联系,不然我也不会一直提起上周那题。仔细想想,求解一维数组中最大矩形面积我们已经有了较快的解法,那么我们可以考虑把从二维数组求解转变成从一维数组求解。
我们从上往下,一行行来分解二维矩阵,就可以把问题转变成求m次一维数组的最大矩形面积(m为行数):以一个一维数组来存放高度,当遍历到下一行时,从左往右遍历每一列位置,如果该位置为0,则高度为0;否则高度为上一行求得的高度+1。
例如,在例子中,遍历到每一行时高度分别为:
["1","0","1","0","0"],
["2","0","2","1","1"],
["3","1","3","2","2"],
["4","0","0","3","0"]
运用上一周的算法即可算出答案。
代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int maximalRectangle(vector<vector<char> >& matrix) {
if (matrix.size() == 0) return 0;
int result = 0;
vector<int> heights(matrix[0].size(), 0);
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
if (matrix[i][j] == '0') heights[j] = 0;
else heights[j]++;
}
result = max(result, largestRectangleArea(heights));
}
return result;
}
int largestRectangleArea(vector<int>& heights) {
int result = 0;
int n = heights.size();
if (n == 0) return 0;
int left[n], right[n];
left[0] = -1;
right[n - 1] = n;
for (int i = 1; i < n; ++i) {
if (heights[i] > heights[i - 1]) left[i] = i - 1;
else {
//找第一个小于当前元素的元素下标
int tmp = left[i - 1];
while (heights[i] <= heights[tmp] && tmp != -1) {
tmp = left[tmp];
}
left[i] = tmp;
}
}
for (int i = n - 2; i >= 0; --i) {
if (heights[i] > heights[i + 1]) right[i] = i + 1;
else {
//找第一个小于当前元素的元素下标
int tmp = right[i + 1];
while (heights[i] <= heights[tmp] && tmp != n) {
tmp = right[tmp];
}
right[i] = tmp;
}
result = max(result, (right[i] - left[i] - 1) * heights[i]);
}
result = max(result, (right[n - 1] - left[n - 1] - 1) * heights[n - 1]);
return result;
}
};
static int x = []() {
ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
复杂度分析
这个解法的复杂度重点在于求最大矩形面积的算法,在上周我们已经分析过,算法由于while循环的次数可以很少,因此算法时间复杂度可以逼近O(n),空间复杂度O(2n) = O(n)。
因此这个解法的时间复杂度逼近O(mn),空间复杂度为O(3n) = O(n),其中m为matrix行数,n为matrix列数。
另外,在提交后查看别人的代码时,我发现了这么一段代码:
static int x = []() {
ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
这段代码通过关闭cout与printf之间的同步、解除cin与cout之间的绑定提高了C++的IO效率。详情参见:
https://blog.csdn.net/chenf1999/article/details/84452273
在这么做之后,这个解法在leetcode上运行时间为8ms。
解法二
采用动态规划的思想。我们考虑对二维矩阵中的每一个点 ( i , j ) (i, j) (i,j)去寻找一个最大矩形,从这个点向上连续的1个数为矩形的高,再向左右两边扩展得到边界,因此这样的矩形有3个参数:
height, left right
,通过这3个参数就可以计算出矩形面积。
对每一行可以维护这3个参数的数组,值的更新与上一行的数据有关。对于点 ( i , j ) (i, j) (i,j),更新
height[j]
比较简单:
更新
left
和
right
稍微麻烦一点,更新它们要同时考虑到本行和上一行的数据。好在通过动态规划,我们存储了点 ( i − 1 , j ) (i-1 ,j) (i−1,j)的
left
和
right
,可以维护两个变量
curLeft
和
curRight
来记录当前行的0的位置。更新
left
的方法为:
curLeft
如何维护呢?在遍历到0时,
curLeft
就记录这个0的位置(可以加1来代表1的位置,作为边界);与之相反,
curRight
则不需要减1,即边界是左闭右开的区间,这样就可以直接通过
height * (right - left)
来计算面积。
需要注意,除了在遍历到1时需要更新
left
,在遍历到0时也要将
left
置为初始值,因为 ( i , j ) (i, j) (i,j)这个位置一旦为0,就与 ( i − 1 , j ) (i-1, j) (i−1,j)的最大矩形无关了,之前维护的
left
和
right
都不再对下面那些行的数据有影响。
代码
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (!matrix.size() || !matrix[0].size()) return 0;
int n_col = matrix[0].size();
vector<int> left(n_col, 0), right(n_col, n_col), height(n_col, 0);
int result = 0;
for (int i = 0; i < matrix.size(); ++i) {
int curLeft = 0, curRight = n_col;
for (int j = 0; j < n_col; ++j) {
if (matrix[i][j] == '1') {
height[j] = height[j] + 1;
left[j] = max(left[j], curLeft);
}
else {
height[j] = 0;
curLeft = j + 1;
left[j] = 0;
}
}
for (int j = n_col-1; j >= 0; --j) {
if (matrix[i][j] == '1') {
right[j] = min(right[j], curRight);
result = max(result, height[j] * (right[j] - left[j]));
}
else {
curRight = j;
right[j] = n_col;
}
}
}
return result;
}
};
复杂度分析
动态规划的时间复杂度很容易看出来是 O ( n m ) O(nm) O(nm),空间复杂度是 O ( m ) O(m) O(m), m m m为列数。