C++ O(mn2) solution using a stack


  • 0
    X
    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            if(0==matrix.size()){return  0;}
            stack<int> st={};
            st.push(-1);
            int height[matrix[0].size()]={0};
            int max=0;
            for(int i=0;i<matrix.size();i++){
                for(int j=0;j<matrix[0].size();j++){
                    if(matrix[i][j]=='1'){
                        height[j] += 1;
                    }else{
                        height[j]=0;
                    }
                    while(st.top()!=-1&&height[j]<=height[st.top()]){
                        int tmp = st.top();
                        st.pop();
                        max = std::max(max,height[tmp]*(j-st.top()-1));
                    }
                    st.push(j);
                }
                while(st.top()!=-1){
                    int tmp = st.top();
                    st.pop();
                    int tmp2 = height[tmp]*(matrix[0].size()-st.top()-1);
                    max=std::max(max,tmp2);
                }
            }
            return max;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.