leetcode 84. 柱状图中最大的矩形

题目描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。

histogram

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

histogram_area

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:
输入: [2,1,5,6,2,3]
输出: 10

题解

暴力破解法,计算所有的两个柱子之间的最大矩形面积

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func largestRectangleArea(heights []int) int {
res := 0
n := len(heights)
for i := 0; i < n; i++ {
minHeight := heights[i]
res = max(res, minHeight)
for j := i+1; j < n; j++ {
minHeight = min(minHeight, heights[j])
res = max(res, minHeight * (j-i+1))
}
}
return res
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func max(a, b int) int {
if a > b {
return a
}
return b
}