LeetCode 85. 最大矩形***

用矩阵前缀和统计会超时，直接变成 O ( n 4 ) O(n^4) O(n4)复杂度，最后三个用例过不了；

可以进行逐列计算，每列的值代表该列左边有多少个1，此时这个题变成了柱形能够拼成的最大矩形面积问题；

那道题用单调栈做，看了一下，又忘了；

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        int maxn=0;
        vector>dp(m,vector(n+1,0));
        for(int j=1;j<=n;j++){
            vectorvec;
            for(int i=0;i
                if(matrix[i][j-1]=='0'){
                    dp[i][j]=0;
                }else{
                    dp[i][j]=dp[i][j-1]+1;
                }
                vec.push_back(dp[i][j]);
            }
            stackst;
            vec.insert(vec.begin(), 0);
            vec.push_back(0);
            for(int i=0;i
                while(!st.empty()&&vec[st.top()]>vec[i]){
                    int index=st.top();
                    st.pop();
                    int left=st.top()+1;
                    maxn=max(maxn,(i-left)*vec[index]);
                }
                st.push(i);
            }
        }
        return maxn;
    }
};