力扣85.最大矩形

力扣85.最大矩形

• 

  • 遍历所有行作为底边 做求矩形面积（84.

•   class Solution {public:int maximalRectangle(vector<vector<char>>& matrix) {if (matrix.empty()) return 0;int n = matrix.size(),m = matrix[0].size();int res=0;vector<int> line(m+2,0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)  line[j] = matrix[i-1][j-1] == '0' ? 0 : line[j] + 1;res = max(res,cul(line));}return res;}int cul(vector<int>& h){int res = 0;stack<int> st;int m = h.size();vector<int> l(m,-1),r(m,m);for(int j=0;j<m;j++){while(!st.empty() && h[j] <= h[st.top()]) st.pop();if(!st.empty()) l[j] = st.top();st.push(j);}for(int j=m-1;j>=0;j--){while(!st.empty() && h[j] <= h[st.top()]) st.pop();if(!st.empty()) r[j] = st.top();st.push(j);}for(int j=0;j<m;j++)res = max(res, (r[j] - l[j] - 1) * h[j]);return res;}};