Leetcode-Hard 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.

image

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

image

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

思路

用栈来模拟，遍历heights数组，如果大于栈顶元素，就push进去；否则，持续弹栈来计算从栈顶点到降序点的矩阵大小。然后将这一部分全部替换为降序点的值，即做到了整体依然是有序非降的。

整个过程中，即把所有的局部最大矩阵计算过了，又在宽度范围内保留了全部的场景。

代码实现

class Solution:
    def largestRectangleArea(self, height):
        height.append(0)
        stack = [-1]
        ans = 0
        for i in range(len(height)):
            while height[i] < height[stack[-1]]:
                h = height[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)
            stack.append(i)
        height.pop()
        return ans