[LeetCode] Maximal Rectangle

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<vector<char> > &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方向最小的iint minI = i-1;while(minI >=0 && matrix[minI][j-1]=='1') minI–;minI = max(minI, 0);//找到j方向最小的jint 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<vector<char>>& 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<vector<char> > &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<vector<char> > &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<n; i++){h[i] = 0;}int result = 0;for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(matrix[i][j]=='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));}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)的时间复杂度做完，用到栈的思想，具体见，这道题是计算直方图的最大面积。下面是代码：

class Solution {public:int maximalRectangle(vector<vector<char> > &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<m; i++){stack<int> s;int tempMax = 0;//某一行最大的areabool 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()]<h[j]){ //入栈s.push(j);hCounted = false;}else{//h多申请了一个空间，并赋值为0，，保证会最终会执行到此步int temp = s.top();s.pop();tempMax = max(tempMax, h[temp] * (s.empty() ? j : (j – s.top() – 1)));j–; //这里j不变，表示找出所有大于当前的，并出栈}}result = max(result, tempMax);}delete[] h;return result;}private:int max(int a, int b){return a>b ? a : b;}};

走一个地方停一个地方。在我心里最美好的就是和你一起老在路上，