AC Python DP solutioin 120ms based on largest rectangle in histogram


  • 34
    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        height = [0] * (n + 1)
        ans = 0
        for row in matrix:
            for i in xrange(n):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            stack = [-1]
            for i in xrange(n + 1):
                while height[i] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = i - 1 - stack[-1]
                    ans = max(ans, h * w)
                stack.append(i)
        return ans
    
    # 65 / 65 test cases passed.
    # Status: Accepted
    # Runtime: 120 ms
    # 100%
    

    The solution is based on largest rectangle in histogram solution. Every row in the matrix is viewed as the ground with some buildings on it. The building height is the count of consecutive 1s from that row to above rows. The rest is then the same as this solution for largest rectangle in histogram


  • 0
    S
    This post is deleted!

  • 0
    C

    we people all have the same thoughts but this implementation is beautiful.


  • 0

    Glad you like it.


  • -1

    Great implementation, I really like your coding style. Also explanation is brief and to the point but explanatory.


  • 0
    G

    Thanks for the links to Largest Rectangle in Histogram problem and your solution to it.


  • 0
    L

    amazing !! Thanks so much for those sharing


  • 0
    C

    I don't understand this "The building height is the count of consecutive 1s from that row to above rows." What if the row is 1 0 0 1 1 1 0 0 1 1 1 1 1. Is building height 5 in this case since that is the maximum number of consecutive 1?


  • 0

    you're so smart!


  • 1

    You are soooooo smart!
    Thank you for you clear explanation.


  • 0
    A

    Thanks, the stack implementation here is brilliant!


Log in to reply
 

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