LeetCode 84. Largest Rectangle in Histogram 直方图最大矩形覆盖

题目

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

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.

Example:

讲解

我们引入一个栈来解决这个问题。首先,把一个假的索引-1推进栈里面。然后依次加入数组中的索引,当出现两个连续高度下降的柱子时候,我们开始取出栈顶索引比计算矩形面积,直到heights[stack.peek()] ≤ heights[i],计算矩形面积:heights[stack.pop()] * (i − stack.peek() − 1)。

视频教学

Java代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注