LeetCode: Largest Rectangle in Histogram 解题报告

时间:2022-08-30 21:00:28

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.

LeetCode: Largest Rectangle in Histogram   解题报告

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

LeetCode: Largest Rectangle in Histogram   解题报告

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

For example,
Given height = [2,1,5,6,2,3],
return 10.

SOLUTION 1:

http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html

使用递增栈来处理。每次比较栈顶与当前元素。如果当前元素小于栈顶元素,则入站,否则合并现有栈,直至栈顶元素小于当前元素。结尾入站元素0,重复合并一次。

1. 当遇到一个违反递增关系的元素时,例如:

2, 1, 5, 6, 2, 3

(1). S: 2

(2).   S: 2    新的元素1比2要小,表示Index = 0的这个直方图的右边界到达了,我们可以计算以它高度的最大直方。那么这个宽度如何计算呢?

i = 1,   而2弹出后,栈为空,宽度是从i到最左边(因为这是一个递增栈,如果现在栈为空,表示我们取出的当前直方是最低的直方,它的宽度可以一直延展到最左边。)

假如栈不为空,则宽度是 i - s.peek() - 1 (因为要减去s.peek()这个直方本身,它比s.pop()要低,阻止了s.pop()这个直方向左边延展)

2 弹出后,栈为空。

(3).  S: 1, 5, 6(这三个是连续递增,就让它们一直入栈)

(4).  S: 1, 5, 6 现在我们遇到2, 6 出栈,它的宽度是6本身(i - 5所在的索引- 1)。5出栈,宽度是i - 1所在的索引 - 1

(5).  因为2比1要高,所以我们停止计算直方,把2继续入栈。然后3入栈。

(6).  这时index = len. 我们直接到第二个分支,把1, 2, 3 这三个直方计算了。

(7).  栈为空,index = len 会入栈,然后index++ 越界,下一次就退出了。这里我们不可以把index < len 放在第一个判断的前面来判断,因为这样的话,当index = len,

会直接再进入第二个分支,引发越界错误。其实我们就是假设在整个直方的最后存在一个height = 0的直方,所以我们要在一直计算到Index = len为止。而且因为它高度为0比谁都要低,所以可以把这个索引直接入栈。

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/array/LargestRectangleArea.java