esc to dismiss

84. 柱状图中最大的矩形

题目

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

解体思路

以一根柱子的高为基准高能圈出的最大面积应该是向左右扩展,直到遇到比该柱子低之前的柱子,左右两个柱子圈出的面积就是该柱子高的最大面积,然后比较所有柱子的最大面积,求得的最大面积即为答案。

而找出柱子左右最近的比它低的柱子的方法可以用单调栈 法。

经验教训

本题我是在看单调栈的介绍时做的题目,因此脑中有了单调栈先入为主的概念,反倒忽略了理解题目的意思,以至于出了些低级错误。

由于Go语法不熟前面几次提交都出错了,Go语法的一些教训:

make slice 的参数有三个:slice, len, cap

stack := make([]int, len(heights)) // 这样是分配了 len = cap = len(heights)

stack := make([]int, 0, len(heights)) // 这样是分配了 len = 0, cap = len(heights)

for ... range 第一个参数是 index

for s := range stack { // 这个 s 取得其实是循环的 index,而不是 item
    widths[s] = s + 1
}

for _, s := range stack { // 这个 s 才是 item
    widths[s] = s + 1
}
x