LeetCode | Maximal Rectangle

本文主要是介绍LeetCode | 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.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

参考：http://blog.csdn.net/doc_sgl/article/details/11832965

CSDN的MarkDown编辑器做的还是太难用了，然后发现html编辑器简直治愈，不说了入坑。。

首先这道题能想到以类似https://leetcode.com/problems/largest-rectangle-in-histogram/这道题的解法，表示对该博主表示佩服佩服。

相比较一维的最大矩形问题，这道题拓展到了二维，考虑每一行向下可以扩展的区域，可以构成类似一个倒置的直方图。

例如对于题目给的用例，第一行可以组成如下的直方图：

而对于第二行，则有类似的情况，如下

并且在这一行，我们可以得到所需要的最大值。

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int m=matrix.size();if(!m) return 0;int n=matrix[0].size();int dp[m+1][n+2];memset(dp,0,sizeof(dp));for(int j=0;j<n;j++)if(matrix[0][j]=='1') dp[0][j]=1;for(int j=0;j<n;j++){for(int i=1;i<m;i++){if(matrix[i][j]=='1') dp[i][j]=dp[i-1][j]+1;}}//完成对dp数组的初始化// 对每一行作为起始点进行遍历int maxRect=0;for(int i=0;i<m;i++){maxRect=max(maxRect,largestRectangleArea(dp[i],n));}return maxRect;}int largestRectangleArea(int heights[],int n) {stack<int> Q;int i=0,maxV=0;heights[n++]=0;while(i<n){if(Q.empty() || heights[i]>=heights[Q.top()])Q.push(i++);else{int h=Q.top();Q.pop();//这里的判断非常关键，如果是栈内最后一个元素，则不应当计算一段区间而应当计算从0开始所有的高度int area=(Q.empty()?i:i-Q.top()-1)*heights[h];maxV=max(maxV,area);}}return maxV;}
};

这篇关于LeetCode | Maximal Rectangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---