It seems the testing data is a bit too weak. The following O(n^3) solution got accepted with 16 ms...


  • 0
    H
    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            int m = matrix.size();
            if (!m) return 0;
            int n = matrix[0].size();
            if (!n) return 0;
            
            vector<int> h(n+2, 0);
            int best = 0;
            for (int i = 0 ; i < m ; i++) {
                for (int j = 0 ; j < n ; j++)
                    h[j+1] = matrix[i][j] == '1' ? h[j+1]+1 : 0;
                //for (int j = 1 ; j <= n ; j++) cout<<h[j]<<",";
                //cout<<endl;
            
                for (int m = 1 ; m <= n ; m++) {
                    if (h[m] == 0) continue;
                    int l = m;
                    while (h[l] >= h[m]) l--;
                    int r = m;
                    while (h[r] >= h[m]) r++;
                    int area = (r - l - 1) * h[m];
                    if (area > best) best = area;
                }
            }
            return best;
        }
    };
    

    For comparison, the O(n^2) solution using stack costs 20 ms:

    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            int m = matrix.size();
            if (!m) return 0;
            int n = matrix[0].size();
            if (!n) return 0;
            
            vector<int> h(n+2, 0);
            int best = 0;
            for (int i = 0 ; i < m ; i++) {
                for (int j = 0 ; j < n ; j++)
                    h[j+1] = matrix[i][j] == '1' ? h[j+1]+1 : 0;
                //for (int j = 1 ; j <= n ; j++) cout<<h[j]<<",";
                //cout<<endl;
                stack<int> st;
                st.push(0);
                for (int r = 1 ; r <= n+1 ; r++) {
                    int m = st.top();
                    while (h[m] > h[r]) {
                        st.pop();
                        int l = st.top();
                        int area = (r - l - 1) * h[m];
                        if (area > best) best = area;
                        m = l;
                    }
                    
                    if (h[r] == h[m]) st.top() = r; else st.push(r);
                }
                
                /*
                for (int m = 1 ; m <= n ; m++) {
                    if (h[m] == 0) continue;
                    int l = m;
                    while (h[l] >= h[m]) l--;
                    int r = m;
                    while (h[r] >= h[m]) r++;
                    int area = (r - l - 1) * h[m];
                    if (area > best) best = area;
                }*/
            }
            return best;
        }
    };

Log in to reply
 

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