LeetCode: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.

分析：一般一個題目我首先會想想怎么暴力解決，比如這一題，可以枚舉出所有的矩形，求出其中的面積最大者，那么怎么枚舉呢，如果分別枚舉矩形的寬度和高度，這樣還得枚舉矩形的位置，復(fù)雜度至少為O(n^4) (計算復(fù)雜度是我們把matrix的行、列長度都泛化為n，下同)，我們可以枚舉矩形左上角的位置，那么知道了矩形左上角的位置，怎么計算以某一點為左上角的矩形的最大面積呢？舉例如下，下面的矩陣我們以(0,0)為矩形的左上角：

1 1 1 1 0 0

1 1 1 0 1 1

1 0 1 0 1 1

0 1 1 1 1 1

1 1 1 1 1 1

矩形高度是1時，寬度為第一行中從第一個位置起連續(xù)的1的個數(shù)，為4，面積為4 * 1 = 4

矩形高度是2時，第二行從第一個位置起連續(xù)1的個數(shù)是3，寬度為min(3,4) = 3，面積為3*2 = 6

矩形高度為3時，第三行從第一個位置起連續(xù)1的個數(shù)是1，寬度為min(1,3) = 1，面積為1*3 = 3

矩形高度為4時，第四行從第一個位置起連續(xù)1的個數(shù)是0，寬度為min(0,1) = 0，面積為0*4 = 0

后面的行就不用計算了，因為上一行計算的寬度是0，下面所有寬度都是0

因此以(0,0)為左上角的矩形的最大面積是6，計算以某一點為左上角的矩形的最大面積復(fù)雜度是O(n)。

注意到上面我們用到了信息“從某一行某個位置開始連續(xù)的1的個數(shù)”，這個我們可以通過動態(tài)規(guī)劃求得：設(shè)dp[i][j]是從點(i,j)開始，這一行連續(xù)1的個數(shù)，動態(tài)規(guī)劃方程如下：本文地址

初始條件：dp[i][column-1] = (matrix[i][column-1] == '1') （column是matrix的列數(shù)）
dp[i][j] = (matrix[i][j] == '1') ? 1 + dp[i][j + 1] : 0 ，(從方程看出我們應(yīng)該從每一行的后往前計算)

計算dp復(fù)雜度O(n^2)，枚舉左上角位置以及計算以該位置為左上角的矩形最大面積復(fù)雜度是O(n^2*n)=O(n^3)，總的復(fù)雜度是O(n^3)

這個算法還可以優(yōu)化，枚舉到某個點時我們可以假設(shè)該點右下方全是1，得到一個假設(shè)最大面積，如果這個面積比當(dāng)前計算好的面積還要小，該點就可以直接跳過；在上面計算以某點為左上角的矩形面積時，也可以剪枝，剪枝方法同上。具體可以參考代碼注釋。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

classSolution { public: intmaximalRectangle(vector<vector<char> > &matrix) { introw = matrix.size(); if(row == 0)return0; intcolumn = matrix[0].size(); intdp[row][column], res = 0; memset(dp, 0, sizeof(dp)); //求出所有的dp值 for(inti = 0; i < row; i++) dp[i][column-1] = (matrix[i][column-1] == '1'); for(inti = 0; i < row; i++) for(intj = column - 2; j >= 0; j--) if(matrix[i][j] == '1') dp[i][j] = 1 + dp[i][j + 1]; //以每個點作為矩形的左上角計算所得的最大矩形面積 for(inti = 0; i < row; i++) { for(intj = 0; j < column; j++) { //剪枝，column-j是最大寬度，row-i是最大高度 if((column - j) * (row - i) <= res)break; intwidth = dp[i][j]; for(intk = i; k < row && width > 0; k++) { //剪枝,row-i是以點(i,j)為左上角的矩形的最大高度 if(width * (row - i) <= res)break; //計算以(i.j)為左上角，上下邊緣是第i行和第k行的矩形面積 if(width > dp[k][j])width = dp[k][j];//矩形寬度要取從第i行到第k行寬度的最小值 res = max(res, width * (k - i + 1)); } } } returnres; } };

O(n^2)的解法：

回想leetcode的另一題計算直方圖最大面積：Largest Rectangle in Histogram，它可以在O(n)時間內(nèi)解決，這一題可以轉(zhuǎn)化成求直方圖最大面積問題，對每一行中的每個位置，計算該位置所在列向上的1的連續(xù)個數(shù)，這樣每一行中每個位置1的個數(shù)就形成了一個直方圖，對每一行調(diào)用計算直方圖面積的算法，就可以求出最大的面積。下面代碼中height就是保存每一行每個位置1的個數(shù)，并且和上面解法中求dp類似，每一行的height可以由上一行的height求得。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

classSolution { public: intmaximalRectangle(vector<vector<char> > &matrix) { introw = matrix.size(); if(row == 0)return0; intcolumn = matrix[0].size(); intheight[column+1], res = 0; memset(height, 0, sizeof(height)); stack<int> S; for(inti = 0; i < row; i++) { stack<int>().swap(S);//清空棧 boolflag = false;//防止同一height[j]被多次更新 for(intj = 0; j <= column; j++) { if(j < column && flag == false) {//更新當(dāng)前行第j列的height值 if(matrix[i][j] == '1') { if(i-1 >=0 && matrix[i-1][j] == '1') height[j]++; elseheight[j] = 1; } elseheight[j] = 0; } if(S.empty() || height[j] > height[S.top()]) { S.push(j); flag = false; } else { inttmp = S.top(); S.pop(); res = max(res, height[tmp] * (S.empty() ? j : j-S.top()-1)); j--; //保持此次循環(huán)中j不變 flag = true;//height[j]已經(jīng)更新，無需再次更新 } } } returnres; } };

其實第一種解法也包含求直方圖最大面積的思想，我們只是把直方圖順時針旋轉(zhuǎn)了90度，大家可以好好想想看。

【版權(quán)聲明】轉(zhuǎn)載請注明出處：http://www.cnblogs.com/TenosDoIt/p/3454877.html

分類:算法與數(shù)據(jù)結(jié)構(gòu),OJ,LeetCode
標(biāo)簽:leetcode

總結(jié)

以上是生活随笔為你收集整理的Maximal Rectangle的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。