84. Largest Rectangle in Histogram

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.

屏幕快照 2017-12-06 下午5.54.03.png

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

题目大意

给定一数组代表直方图的矩形条高度,每个矩形条的宽度为1,在直方图种找到最大矩形的面积,如上图中例子所示。

解题思路

遍历矩形条高度,计算以当前矩形条为高度的最大面积(即要维持一个递增序列)
使用Stack构建递增序列,比栈顶小的值则弹出,并计算其面积,否则压栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func largestRectangleArea(_ heights: [Int]) -> Int {
var stack = [Int]()
var ans = 0
let heights = heights + [-1]
for (i, h) in heights.enumerated() {
while let last = stack.last, h <= heights[last] {
stack.removeLast()
let w = stack.isEmpty ? i : i - stack.last! - 1
ans = max(ans, w * heights[last])
}
stack.append(i)
}
return ans
}
0%