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;
}
};
