def largestRectangleArea_error(self, height):
        """
        O(n)

        Algorithm: Stack.

        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

        length = len(height)
        global_max = -1<<32
        inc_stack = []  # store the pointer

        i = 0
        while i<length:
            if not inc_stack or height[i]>=height[inc_stack[-1]]:
                inc_stack.append(i)
                i += 1
            else:
                last = inc_stack.pop()
                if inc_stack:
                    area = height[last] * (i-last)
                else:
                    area = height[last] * i
                global_max = max(global_max, area)

        # remaining stack
        while inc_stack:
            last = inc_stack.pop()
            if inc_stack:
                area = height[last]*(i-last)
            else:
                area = height[last]*i
            global_max = max(global_max, area)
        return global_max
dataset/ETHPy150Open algorhythms/LeetCode/082 Largest Rectangle in Histogram.py/Solution.largestRectangleArea_error/original