leetcode: 84. Largest Rectangle in Histogram

# Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
# find the area of largest rectangle in the histogram.

# Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

# The largest rectangle is shown in the shaded area, which has area = 10 unit.
#
# For example,
# Given heights = [2,1,5,6,2,3],
# return 10.

仔细考察Brute Force算法，发现问题在于指针重复扫描。以递增序列为例：

0 1 2 3 4 5 6

在计算s[0]的时候扫描了右边6个数，计算s[1]时继续扫描右边5个数，依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时，bar i~j的面积一定都能扩展到j。而一旦在j+1递减了，那么表示bar i~j中的部分bar k无法继续扩展，条件是h[k]>h[j+1]。

1. 利用这个性质，可以将递增序列cache在一个stack中，一旦遇到递减，则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k，并计算面积。

2. 由于面积的计算需要同时知道高度和宽度，所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度，而反之则不行。

class Solution():
    def largestRectangleArea(self, xs):
        xs.insert(0, 0)
        xs.append(0)
        stack, maxArea = [], 0
        for i, x in enumerate(xs):
            if not stack or xs[stack[-1]] <= x:
                stack.append(i)
            else:
                while stack and xs[stack[-1]] > x:
                    maxArea = max(maxArea, xs[stack[-1]]*(i-stack[-2]-1))
                    stack.pop()
                stack.append(i)
        right = stack[-1]
        stack.pop()
        while len(stack) > 1:
            offset = right-stack[-1]
            maxArea = max(maxArea, xs[stack[-1]]*offset)
            stack.pop()
        return maxArea


if __name__ == "__main__":
    assert Solution().largestRectangleArea([2, 0, 2]) == 2
    assert Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10