?
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. 解题思路; 题意表示找到右全1形成的最大的矩形块。 解法1： 用动态规划做，若d[i][j]表示以matrix[i][j]为右下角的矩形区域中，满足条件的最大矩形块。若matrix[i][j]=='0'，则d[i][j] = max(d[i-1][j], d[i][j-1])，若matrix[i][j]=='1'，则d[i][j] = max(d[i-1][j], d[i][j-1], 包含matrix[i][j]且以之为右下角的最大矩形块)。但是如何求“包含matrix[i][j]且以之为右下角的最大矩形块”呢？我最开始想到蛮力法，代码如下所示：
class Solution {
public:
int maximalRectangle(vector
> &matrix) {
int m = matrix.size();
if(m == 0){
return 0;
}
int n = matrix[0].size();
if(n==0){
return 0;
}
int** d=new int*[m + 1];
for(int i=0; i<=m; i++){
d[i]=new int[n + 1];
}
for(int i=0; i<=m; i++){
d[i][0]=0;
}
for(int i=0; i<=n; i++){
d[0][i]=0;
}
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
d[i][j]=max(d[i-1][j], d[i][j-1]);
if(matrix[i-1][j-1]=='1'){
//计算以i-1,j-1元素为右下角的最大全1矩阵的面积
//找到i方向最小的i
int minI = i-1;
while(minI >=0 && matrix[minI][j-1]=='1') minI--;
minI = max(minI, 0);
//找到j方向最小的j
int minJ = j-1;
while(minJ >=0 && matrix[i-1][minJ]=='1') minJ--;
minJ = max(minJ, 0);
if((i - minI)*(j - minJ) > d[i][j]){
int maxArea = 0;
for(int tempI = minI; tempI < i; tempI++){
for(int tempJ = minJ; tempJ < j; tempJ++){
int area = getArea(matrix, tempI, i-1, tempJ, j-1);
if(area!=0){
maxArea = max(area, maxArea);
break;
}
}
}
d[i][j]=max(d[i][j], maxArea);
}
}
}
}
int result = d[m][n];
for(int i=0; i<=m; i++){
delete[] d[i];
}
delete[] d;
return result;
}
private:
int max(int a, int b){
return a>b?a:b;
}
int getArea(vector
>& matrix, int startI, int endI, int startJ, int endJ){ bool allOne = true; for(int i=startI; i<=endI; i++){ for(int j=startJ; j<=endJ; j++){ if(matrix[i][j]=='0'){ allOne = false; break; } } if(!allOne){ break; } } if(allOne){ return (endI - startI + 1) * (endJ - startJ + 1); }else{ return 0; } } };
居然也能通过，但运行时间是874ms，显然是不对的，因为其最坏情况运行时间复杂度为O(m2*n2) 解法2 为了能尽快算出“包含matrix[i][j]且以之为右下角的最大矩形块”，可以记录每一行全1的高度。代码如下：
class Solution {
public:
int maximalRectangle(vector
> &matrix) {
int m = matrix.size();
if(m == 0){
return 0;
}
int n = matrix[0].size();
if(n==0){
return 0;
}
//动态规划数组
int** d=new int*[m + 1];
for(int i=0; i<=m; i++){
d[i]=new int[n + 1];
}
for(int i=0; i<=m; i++){
d[i][0]=0;
}
for(int i=0; i<=n; i++){
d[0][i]=0;
}
//记录全1的高度
int* h = new int[n + 1];
for(int i=0; i<=n; i++){
h[i] = 0;
}
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
d[i][j]=max(d[i-1][j], d[i][j-1]);
if(matrix[i-1][j-1]=='1'){
h[j]++;
int maxArea = h[j];
int minH = h[j];
for(int k=j-1; k>0; k--){
if(h[k] == 0){
break;
}
minH = minH > h[k] ? h[k] : minH;
maxArea = max(maxArea, minH * (j - k + 1));
}
d[i][j] = max(d[i][j], maxArea);
}else{
h[j]=0;
}
}
}
int result = d[m][n];
for(int i=0; i<=m; i++){
delete[] d[i];
}
delete[] d;
delete[] h;
return result;
}
private:
int max(int a, int b){
return a>b?a:b;
}
};
这样，算法的时间复杂度降到了O(m*n*n)，这是坏的情况。在LeetCode中运行时间降到了28ms。 解法3： 后来想，其实我无需记录某个位置的最大值，只需记录全局的最大值，即可以不用动态规划的思想，下面是解法2的改进代码：
class Solution {
public:
int maximalRectangle(vector
> &matrix) {
int m = matrix.size();
if(m == 0){
return 0;
}
int n = matrix[0].size();
if(n==0){
return 0;
}
//记录全1的高度
int* h = new int[n];
for(int i=0; i
=0; k--){ if(h[k] == 0){ break; } minH = minH > h[k] ? h[k] : minH; maxArea = max(maxArea, minH * (j - k + 1)); } result = max(result, maxArea); }else{ h[j]=0; } } } return result; } private: int max(int a, int b){ return a>b?a:b; } };
这样，时间复杂度虽然没有变，但是省去了很大的空间开销，从而也节省了时间。LeetCode的运行时间为19ms 解法4： 在网上查了一下，该题竟然还可以在O(m*n)的时间复杂度做完，用到栈的思想，具体见http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.
html，这道题是计算直方图的最大面积。下面是代码：
class Solution {
public:
int maximalRectangle(vector
> &matrix) {
int m = matrix.size();
if (m == 0){
return 0;
}
int n = matrix[0].size();
if (n == 0){
return 0;
}
int result = 0;
//记录全1的高度
int* h = new int[n+1]; //多申请一个空间，稍后会知道他的好处
for (int i = 0; i<=n; i++){
h[i] = 0;
}
for (int i = 0; i
s; int tempMax = 0; //某一行最大的area bool hCounted = false; for (int j = 0; j<=n; j++){ if(!hCounted&&j!=n){ if (matrix[i][j] == '1'){ h[j]++; } else{ h[j] = 0; } hCounted = true; } if (s.empty() || h[s.top()]
b ? a : b; } };