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.

given height = [2,1,5,6,2,3]

解题方法

brute force方法

对每个bar都遍历之前的bar来找最大rectangle的面积，这样的时间复杂度 是O(n^2)

stack

对于每个bar的最大rectangle面积的计算，如果以当前的bar做为最低的height, 这样我们需要知道的就是左边界和右边界，左右边界也就是第一个比这个bar高度低的bar的index。

而需要知道第一个的位置，也就是最近的index, 可以想到是需要用stack这个data structure, 才能够获得最左边第一个小于它高度的index， 而右边界可以在遍历的过程中得到。

如果我们在遍历时

• 如果当前bar的高度 >= 栈顶的高度，那么就将当前的index push到stack上
• 如果当前bar的高度 <= 栈顶的高度
  • 那么说明当前的index对于栈顶高度来说是一个右边界
  • 将栈顶元素pop,而根据我们对于stack的操作，当前的栈顶index就是Pop出来高度的左边界
  • 计算面积，更新最大面积

注意

• 等于的时候也要push到stack上，如果两个相等高度的bar index不一样，需要更新该高度的index

Solution

class Solution(object):
    def largestRectangleArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0

        stack = []
        maxArea = 0
        length = len(height)

        i = 0
        while i < length:
            if not stack or height[i] >= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                # 将stack顶端的当成smallest bar height
                h = height[stack.pop()]
                if stack:
                    area = h * (i - stack[-1] - 1)
                else:
                    area = h * i
                maxArea = area if area > maxArea else maxArea

        # 最后一个bar还是会Push到stack上，还要计算剩下这些面积
        while stack:
            h = height[stack.pop()]

            if stack:
                area = h * (i - stack[-1] - 1)
            else:
                area = h * i
            maxArea = area if area > maxArea else maxArea

        return maxArea

Reference

• O(nlogn)
• O(n)