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%