题目
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = [] 输出：0
示例 3：
输入：matrix = [["0"]] 输出：0
示例 4：
输入：matrix = [["1"]] 输出：1
示例 5：
输入：matrix = [["0","0"]] 输出：0
解题
方法一：暴力解法
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { int m=matrix.size(),n=matrix[0].size(); vector<vector<int>> width(m,vector<int>(n)); int maxArea=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='1'){ if(j==0){ width[i][j]=1; }else{ width[i][j]=width[i][j-1]+1; } }else{ width[i][j]=0; } int minWidth=width[i][j]; for(int row=i;row>=0;row--){ int height=i-row+1; minWidth=min(minWidth,width[row][j]); maxArea=max(maxArea,height*minWidth); } } } return maxArea; } };
方法二：单调栈
转化为求 84.直方图矩形的最大面积
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { int m=matrix.size(),n=matrix[0].size(); vector<int> heights(n,0); int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]=='0') heights[j]=0; else heights[j]++; } res=max(res,largestRectangleArea(heights)); } return res; } int largestRectangleArea(vector<int> heights){ stack<int> st; int res=0; heights.insert(heights.begin(),0); heights.push_back(0); for(int i=0;i<heights.size();i++){ while(!st.empty()&&heights[i]<heights[st.top()]){ int cur=st.top(); st.pop(); int l=st.top(); int r=i; int width=r-l-1; res=max(res,width*heights[cur]); } st.push(i); } return res; } };
