11 lines 12ms C++ solution


  • 0
    int maximalRectangle(vector<vector<char>>& matrix) {
            int n=(matrix.empty())? 0 : matrix[0].size(), res=0;
            vector<int> left(n,0), right(n, n), height(n,0);
            for(auto mat : matrix)
            {
                int lstart =0, rstart=n;
                for(int j=0; j<n; ++j)
                {
                    height[j] =    (mat[j]=='1') ?       height[j]+1 : 0;
                    left[j] =      (mat[j]=='1') ?       max(left[j], lstart) : min(0, lstart = j+1);
                    right[n-j-1] = (mat[n-j-1] == '1') ? min(right[n-j-1], rstart) : max(n, rstart = n-j-1);
                }
                for(int j=0; j<n; ++j)
                {
                    res = max(res, (right[j]-left[j])*height[j]);
                }
            }
            return res;
        }

  • 0
    Y
    This post is deleted!

  • 0
    Y

    Nice solution :)


  • 0

    @Yuanhui Thank you!


Log in to reply
 

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