Largest Rectangle in Histogram

Question

Thoughts

brute force way

O(n^2) two for loops to find every histogram

对于直方图的每一个右边界，穷举所有的左边界。将面积最大的那个值记录下来。时间复杂度为O(n^2). 单纯的穷举在LeetCode上面过大集合时会超时。 可以通过选择合适的右边界，做一个剪枝(Pruning)。观察发现当height[k] >= height[k - 1]时，无论左边界是什么值，选择height[k]总会比选择height[k - 1]所形成的面积大。 因此，在选择右边界的时候，首先找到一个height[k] < height[k - 1]的k，然后取k - 1作为右边界，穷举所有左边界，找最大面积。

或者可以用另一种方法：最大矩形的高度毫无疑问必然和某一个立柱的高度相等，或者说，最大矩形必然包含了某一个立柱的全部。

因此，可以遍历所有立柱，对当前立柱 i，以其高度左右扩展，看看以当前立柱 i 的高度最多能包含进多大的矩形面积。最后选出最大的总面积即可。

O(n)

refer1 refer2

此解法的核心思想为：一次性计算连续递增的区间的最大面积，并且考虑完成这个区间之后，考虑其前、后区间的时候，不会受到任何影响。也就是这个连续递增区间的最小高度大于等于其前、后区间。

use stack，保存递增高度的index

stack只在当前height比stack top高的时候push,并且保存的是index而不是高度 当前height比stack top小时，pop()并且在pop的过程中计算已pop的height能够得到的rectangle面积，直到stack top比当前的element小，则这个区间计算完毕

因为stack中的height都是递增的，所以计算pop的height能够得到的面积时， 右边的面积可以延伸到当前element的index,而左边则可以延伸的目前stack top所存的index

Solution

class Solution:
    """
    @param height: A list of integer
    @return: The area of largest rectangle in the histogram
    """
    def largestRectangleArea(self, height):
        # write your code here
        if not height:
            return 0
        max = 0
        stack = []
        length = len(height)
        #add an 0, so it would calculate the last height
        height.append(0)
        length += 1
        for i in range(length):
            while stack and height[stack[-1]] > height[i]:
                tmp = stack.pop()
                leftArea = 0
                #left Area include height[tmp] element
                if stack:
                    leftArea = height[tmp] * (tmp - stack[-1])
                else:
                    #to the begining
                    leftArea = height[tmp] * (tmp + 1)
                rightArea = (i - tmp - 1) * height[tmp]
                area = leftArea + rightArea
                if area > max:
                    max = area
            stack.append(i)

        return max