Cacher is the code snippet organizer for pro developers

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = []
        largest = 0
        heights.append(0)
        for i in range(len(heights)):
            # Jsut like a reverse Hanoi Tower, when we encounter a height[i]
            # 1. We pop up all the values in stack that are smaller than height[i], and compute the area for those values.
            # 2. We append height[i] to the stack.
            # Note that if k s.t. `i<k<j` in stack, then height[k] >=height[i] and height[k] >= height[j].
            while len(stack) != 0 and heights[stack[-1]] >= heights[i]:
                temp = stack[-1]
                del stack[-1]
                # for the rectangle with height heights[temp],
                # the left restriction index is stack[-1]
                # the right restriction index is i
                widthLeft = temp if len(stack) == 0 else temp-stack[-1]-1
                # Width between stack[-1]<->temp (both ends exclusive).
                widthRight = i - temp -1
                # Width between temp<->i (both ends exclusive)
                largest = max(largest, (widthLeft+widthRight+1) * heights[temp])
            stack.append(i)
        return largest