85.最大矩形

单调栈，时间复杂度o(mn)，空间复杂度o(mn)

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int m=matrix.size();if(m==0){return 0;}int n=matrix[0].size();//记录矩阵中每个元素左边连续1的数量vector<vector<int>> left(m,vector<int>(n,0));for(int i=0;i<m;i++){for(int j=0;j<n;++j){if(matrix[i][j]=='1'){left[i][j]=(j==0?0:left[i][j-1])+1;}}}int ret=0;//对于每一列，使用基于柱状图的方法，leetcode84for(int j=0;j<n;j++){vector<int> up(m,0),down(m,0);stack<int> stk;for(int i=0;i<m;++i){while(!stk.empty()&&left[stk.top()][j]>=left[i][j]){stk.pop();}up[i]=stk.empty()?-1:stk.top();stk.push(i);}stk=stack<int>();for(int i=m-1;i>=0;i--){while(!stk.empty()&&left[stk.top()][j]>=left[i][j]){stk.pop();}down[i]=stk.empty()?m:stk.top();stk.push(i);}for(int i=0;i<m;++i){int height=down[i]-up[i]-1;int area=height*left[i][j];ret=max(ret,area);}}return ret;}
};