Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
84. Largest Rectangle in Histogram.go
84. Largest Rectangle in Histogram_test.go
README.md

README.md

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.

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:

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

题目大意

给出每个直方图的高度,要求在这些直方图之中找到面积最大的矩形,输出矩形的面积。

解题思路

用单调栈依次保存直方图的高度下标,一旦出现高度比栈顶元素小的情况就取出栈顶元素,单独计算一下这个栈顶元素的矩形的高度。然后停在这里(外层循环中的 i--,再 ++,就相当于停在这里了),继续取出当前最大栈顶的前一个元素,即连续弹出 2 个最大的,以稍小的一个作为矩形的边,宽就是 2 计算面积…………如果停在这里的下标代表的高度一直比栈里面的元素小,就一直弹出,取出最后一个比当前下标大的高度作为矩形的边。宽就是最后一个比当前下标大的高度和当前下标 i 的差值。计算出面积以后不断的更新 maxArea 即可。

You can’t perform that action at this time.