Accepted O(n) Python solution using stack


  • 2
    X
    class Solution:
        # @param height, a list of integer
        # @return an integer
        def largestRectangleArea(self, height):
            #linearly scan the array, keep a stack
            #if the stack is empty or cur > top of the stack, push cur to the stack
            #else cur <= top of the stack, set cur as bar, pop item from the stack until top of the stack < cur
            #for popped item, left index = index of its previous item in the stack, right index = index of bar
            #tail case: for rest of the items in the array, set the top of the stack as bar
            #           pop all the items, left index = index of its previous, right index = index of bar
            if height == []: return 0
            stack = []
            result = 0
            for i in range(0, len(height)):
                if stack != [] and height[i] <= stack[-1][0]:
                    bar = height[i]
                    while stack != [] and stack[-1][0] >= bar:
                        cur = stack.pop()
                        if stack == []:
                            prev = -1   #no previous item, left index = -1
                        else:
                            prev = stack[-1][1]
                        result = max(result, cur[0]*( (i-1) -prev))
                stack.append((height[i], i))
                
            bar = stack[-1]
            while stack != []:
                cur = stack.pop()
                if stack == []:
                    prev = -1   #no previous item, left index = -1
                else:
                    prev = stack[-1][1]
                result = max(result, cur[0]*(bar[1]-prev))
            return result
    

    Please see comments for explanation.


  • 0
    S

    Tail case doesn't work well. Try height = [1, 2, 3, 4, 5].


  • 0
    A

    Inspired by yours. here's my version

    # find the how many bars can extend to right
    def extendBar(self, bar):
        size = len(bar)
        stack = [0]
        extend = [0] * size
        for i in xrange(1, size):
            while len(stack) > 0 and bar[i] < bar[stack[-1]]:
                top = stack.pop()
                extend[top] = i - 1
            stack.append(i)
        
        while stack:
            top = stack.pop()
            extend[top] = size - 1
        
        for i in xrange(size):
            extend[i] = extend[i] - i
        
        return extend
    
    def largestRectangleArea(self, height):
        size = len(height)
        ans = 0
        if size == 0:
            return 0
            
        extend_right = self.extendBar(height)
        extend_left = self.extendBar(height[::-1])
        extend_left = extend_left[::-1]
        
        for i in xrange(size):
            ans = max(ans, height[i] * (extend_right[i] + extend_left[i] + 1))
        
        return ans

Log in to reply
 

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