def largestRectangleArea(self, height):
        """
        O(2*n)
        every bar at most enter the stack once and is popped out once.

        Algorithm: Stack.
        Keep a stack storing the bars increasing order, then calculate the area by popping out the stack to get the
        currently lowest bar which determines the height of the rectangle.

        The popping out is triggered when height being scanned violates increasing order. Keep popping out until not
        violate the increasing order.

        When calculate the area: area = height[last]*( i-(inc_stack[-1]+1) ) rather than area = height[last] * (i-last),
        since originally from inc_stack[-1]+1 to last are higher bars already popped out, which should be included in
        the calculation.

        pay attention to corner case

        reference: http://fisherlei.blogspot.sg/2012/12/leetcode-largest-rectangle-in-histogram.html
        :param height: a list of int
        :return: int
        """
        if not height:
            return 0

        n = len(height)
        gmax = -sys.maxint-1
        inc_stack = []  # store the idx, increasing stack

        for i in xrange(n):
            while inc_stack and height[i] > height[inc_stack[-1]]:
                last = inc_stack.pop()
                if inc_stack:  # calculate area when popping
                    area = height[last]*(i-(inc_stack[-1]+1))
                else:
                    area = height[last]*i
                gmax = max(gmax, area)

            inc_stack.append(i)

        # after processing all heights, process the remaining stack
        i = n
        while inc_stack:
            last = inc_stack.pop()
            if inc_stack:
                area = height[last]*(i-(inc_stack[-1]+1))
            else:
                area = height[last]*i
            gmax = max(gmax, area)

        return gmax
dataset/ETHPy150Open algorhythms/LeetCode/082 Largest Rectangle in Histogram.py/Solution.largestRectangleArea/swapped operands of `>`