Largest Rectangle in Histogram'

Idea

The key idea for my O(n) algorithm is keeping two stacks named position_stack and height_stack while traverse. The definition of stacks is defined in following:(Pay attention the size of the two stacks should keep consistent)

Let the original height array be heights, A equal position_stack[i] , B equal height_stack[i]. This notation means the max height of the qualified rectangle starting at index A(Ending at the current cursor index) in heights is B.

Code

The stack has a little trick in my implementation. I used a sentinel node which is less then all the normal heights and indexed at -1 as the first item in the stacks, to simplify the code when handling the corner case.

class Solution:
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        
        lens = len(heights)
        if lens == 0:
            return 0
        
        position_stack = [-1]
        height_stack = [ -100 ]
        
        index = 0
        max_area = -1
        while index < lens:
            
            while (index < lens and heights[index] >= height_stack[-1]):
                height_stack.append(heights[index])
                position_stack.append(index)
                index += 1
                
            while len(height_stack) > 1 and index < lens and heights[index] <= height_stack[-1]:
                yet_top = height_stack.pop()
                yet_start = position_stack.pop()
                max_area = max(max_area, (index-yet_start)*yet_top )
            
            if index < lens:
                height_stack.append(heights[index])
                position_stack.append(position_stack[-1]+1) 
            
        
        while len(height_stack) > 1:
            yet_height = height_stack.pop()
            yet_start_position = position_stack.pop()
            max_area = max(max_area, (index-yet_start_position)*yet_height )
        
        return max_area