91 ms python solution with constant space


  • 2
    Y
    def largest_rectangle(height):
        n = len(height)
        if n < 2:
            return height[0] if n else 0
    
        height.append(0)
        max_area = 0
        for i in range(0, n + 1):
            j = i - 1
            while j >= 0 and height[j] > height[i]:
                max_area = max(max_area, height[j] * (i - j))
                height[j] = height[i]
                j -= 1
        return max_area

  • 0
    L

    It's concise and like a magic, but I cannot understand the algorithm in your code.
    Why you use 'height[j] = height[i]'
    Could you please explain it?
    I would appreciate if you can explain all.


  • 0
    Y

    In i th iteration, height[j] = height[i] for all j >= 0 and height[j] > height[i] effectively makes height[:i] non decreasing, which is equivalent to using a stack that stores the indices of elements that are in non decreasing order.


  • 0
    P

    In my opinion, this can't be considered as constant space because you reused the input space.


  • 1
    Z

    As "commented" said it is not true constant space

    I modified code a bit to make it really constant space.. And I think it will be easier to read and understand.

    Basically when a height drop detected, the code searches potential largest area that will not be seen as the algorithm goes on running.

    BTW I think this is a greedy algorithm

    def largestRectangleArea(self, height):
        if not height: return 0
    
        lens = len(height)
        height.append(0)    # gurad
        maxArea = 0
        for r in range(0,lens):
            if height[r] > height[r+1]:
                l = r
                minInrange = height[r]
                while height[l] > height[r+1] and l >= 0:
                    minInrange = min(minInrange, height[l])
                    maxArea = max(maxArea, minInrange*(r-l+1))
                    l -= 1
        return maxArea

  • 0
    D

    what's the complexity? Seems to be O(n^2)


Log in to reply
 

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