AC Python clean solution using stack 76ms


  • 41
    def largestRectangleArea(self, height):
        height.append(0)
        stack = [-1]
        ans = 0
        for i in xrange(len(height)):
            while height[i] < height[stack[-1]]:
                h = height[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)
            stack.append(i)
        height.pop()
        return ans
    
    
    
    # 94 / 94 test cases passed.
    # Status: Accepted
    # Runtime: 76 ms
    # 97.34%
    

    The stack maintain the indexes of buildings with ascending height. Before adding a new building pop the building who is taller than the new one. The building popped out represent the height of a rectangle with the new building as the right boundary and the current stack top as the left boundary. Calculate its area and update ans of maximum area. Boundary is handled using dummy buildings.


  • 0
    R

    Not sure, why do you need to height.pop() in the end. Seems redundant to me.


  • 14
    Z

    @rahul8590 Actually this is the most beautiful line of code I see from that program, that line is to recover the original state of the input, since python list is passed by reference instead of shadow copy. It is not gonna give you wrong result for this problem. However in real world development, think about your colleague created a list contains some values that he will need in the future, you added a sentinel value to make your life easier, if you don't clean it up afterward, your colleague's code is very likely to crash. This is a good programming habit, it added one more "redundant" line, but it also make everybody's life easier. Hope it helps


  • 0
    S

    Could someone please explain "w = i - stack[-1] - 1" ?? It would really be helpful.


  • 1
    H

    Genius..............


  • 0
    W

    @shriram2112 Because we did pop first h = height[stack.pop()], so stack[-1] refer to the index before


  • 0
    W

    @rahul8590 I think it does not matter, because we append(0) first, so it just pop it out


  • 0
    T

    What if the heights of the bars is increasing? I think you should include some code handling the boundary case.


  • 0
    C

    @twfx101 I have the exact same doubt as you, haha. Then I run the code, there is actually no problem. Notice that we append 0 to height in the beginning, so the height couldn't be always increasing. It is ensured to goes into while clause.


  • 0
    C

    @shriram2112
    The basic idea behind this algorithm is that we would like to calculate the maximum rectangle (actually not strict in this code , explain later) for every bar i with width r-l-1 and heights[i], where r / l is the index of the first bar in right / left with height lower than bar i. Once we got the maximum rectangle for every bar, the result could be derived by choosing the largest maximum rectangle. Here is a JAVA solution based on this idea (helps a lot for me to understand this python code). Calculating and storing l r will be too cumbersome, so stack is introduced here.

    Back to the problem, the current bar here is stack.pop(), i is the first bar in the right with height lower than current bar and stack[-1] is the first bar in the left with height not higher than current bar (here introduces the non strict maximum with replacing 'lower' to 'not higher', though it wouldn't influence the final result because we will reach that maximum through another bar). In this case, the maximum rectangular of each bar is not calculated one by one along the index, instead bar with peak-like shape will be calculated first. stack stores all the indexes of bars haven't got their maximum rectangular because r is not reached yet.

    The code here is so beautiful and concise, though hard to understand. Hope my explanation help :)


  • 0
    Y
    This post is deleted!

Log in to reply
 

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