leetcode日记（72）最大矩形

依旧是看了答案才知道大概方法…太难想到了

和上一道题思路相似！可以直接调用上题的函数，只不过调用前的准备非常难想到，就是建造形状相同的矩阵，第i行j列的元素是i行中j列前相邻的“1”的个数。

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<int > v(n,0);vector<vector<int>> left(m,v);for(int i=0;i<m;i++){int a=1;for(int j=0;j<n;j++){if(matrix[i][j]=='1'){left[i][j]=a;a++;}else a=1;}}int maxx=left[0][0];vector<int> vec(n,0);left.push_back(vec);for(int j=0;j<n;j++){for(int i=0;i<m;i++){if(left[i][j]>left[i+1][j]){int k=i;for(k;k>=0;k--){if(left[k][j]<left[i+1][j]) break;maxx=max(maxx,left[k][j]*(i-k+1));}for(int x=k+1;x<=i;x++) left[x][j]=left[i+1][j];}}}return maxx;}
};