Easy-to-understand 92ms Python solution, linear time and space.


  • 7
    P
    class Solution(object):
    # Helper function calculating how far each bar can be extended to the right.
    def calmax(self, height):
        stack = []
        n = len(height)
        rec = [0] * n
        for i in xrange(len(height)):
            while len(stack) > 0 and height[stack[-1]] > height[i]:
                top = stack.pop()
                rec[top] = i
            stack.append(i)
        for i in stack:
            rec[i] = n
        return rec
    def largestRectangleArea(self, height):
        # How far can each bar be extended to the right?
        rec1 = self.calmax(height)
        # How far can each bar be extended to the left?
        rec2 = self.calmax(height[::-1])[::-1]
        maxa = 0
        n = len(height)
        for i in xrange(n):
            # Add the left and right part together
            new = height[i] * (rec1[i] + rec2[i] - n)
            maxa = max(new, maxa)
        return maxa
    

    This solution can be made faster. But who cares if the complexity is still \Theta(n)?


  • 0
    A

    Hi, I am not sure how to calculate the time complexity when you are using stack in a loop. Can you explain why it is O(N)?


  • 0
    P

    Every element is pushed and popped exactly once.


Log in to reply
 

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