Answer with Explanations

  • 2
    class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        # Add last height as 0 to make the last part works for stack
        height.append( 0 )
        stack = []
        i = 0
        maxArea = 0
        while i < len(height):
            if stack==[] or height[ stack[-1] ] <= height[i]:
                stack.append( i )
                i = i+1
                num = stack.pop()
                if stack!=[]:
                    area = height[num] * (i - stack[-1] -1)
                    area = height[num] * (i)
                maxArea = max(maxArea, area)


    Step 1: Traverse all possible large rectangles
    Since we need to find the largest rectangle, we need to traversal all possible rectangles and to compare each of the area. But...all possible? There seems to be lots of combinations.
    Actually not!! Because we are only interested in the largest. So for the following example we do not need to consider the blue rectangle. We only need to consider the red one: Why?

    Step 2: Find the nearest smaller value of each bar
    Go back again to the example, the largest private rectangle is the red one not the blue one? Why because for the blue one there's one more bar D which is higher than B. So finding the largest private rectangle is the problem of finding the nearest smaller value. This is actually a classic algorithm problem, which can be find in All Nearest Smaller Values
    The most ideal way to find the nearest smaller value is using stack structure.While traversing the histogram, we push the bar which is higher than the bar at the top of the stack. Therefore, we maintain an ascending stack. In the above example, we have [A, B, C, D] inside stack in ascending order.
    When we reach E, which is shorter than D( stack top ), we pop D. Now, we know for sure D's nearest smaller one is E and C. Similarly, we pop can find the nearest smaller one in B,C as well. Later we push E back to the stack. Now the stack is [A, E], which is still in ascending order. We can find their nearest smaller bar by the same logic.

    S = new empty stack data structure
    for x in the input sequence:
        while S is nonempty and the top element of S is greater than or equal to x:
            pop S
        if S is empty:
            x has no preceding smaller value
            the nearest smaller value to x is the top element of S
        push x onto S

  • 0

    thanks a lot, your article helps me understand the intuition behind the algorithm

Log in to reply

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