医院网站 功能,深圳企业官网网站建设,163邮箱企业邮箱,宁波建设工程学校招生简章84. 柱状图中最大的矩形 正文
题目如下 给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。 求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。 这道题暴力很简单#xff0c;但是时间复杂度是O(N^2)#xf…84. 柱状图中最大的矩形 正文
题目如下 给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。 求在该柱状图中能够勾勒出来的矩形的最大面积。 这道题暴力很简单但是时间复杂度是O(N^2)在这里我们不予考虑我在这里主要介绍一下单调栈的做法。
单调栈主要的思路就是将遍历到的元素下标压入栈中如果当前遍历的元素小于栈顶元素就没有遵循单调的原则需要先把栈中大于当前遍历到的数字的元素弹出再把当前遍历的元素压入栈中在这个过程中我们还需要重新计算最大的矩形面积。
如何计算
首先我们需要明确我们的栈是存储的下标通过下标的差值我们可以计算出宽度而且栈中元素是保持着单调递增的趋势所以我们每次弹出的下标对应的数值都可以作为我们的矩形的高这样便可以计算出我们的矩形面积。
为什么这样做能得出正确答案
首先我们需要先了解一下暴力的做法暴力是通过两个for循环遍历来实现的矩形的面积最大值计算而单调栈是只在每次弹出元素的时候重新计算矩形面积每个元素最多入栈出栈一次所以时间复杂度远小于暴力做法。但我们仔细想一下就能够知道暴力做法是有很多多余的计算步骤的比如以[1,2,3,4,5,6,1]为例子遍历1的时候会把234561遍历完显然效率很低而单调栈在弹出元素时能够确定以当前下标对应的矩形的高的最大面积是多少想清楚这一点这道题就迎刃而解了。
下面是代码
func largestRectangleArea(heights []int) int {var st []intans : 0heights append(heights, -1)for i : 0; i len(heights); i {for len(st) ! 0 heights[i] heights[st[len(st) - 1]] {idx : st[len(st) - 1]st st[:len(st) - 1]var l intif len(st) 0 {l -1} else {l st[len(st) - 1]}ans Max(ans, (i - l - 1) * heights[idx])}st append(st, i)}return ans}func Max(a int, b int) int {if a b {return a}return b}结语
这道题思路来源于bilibili如果觉得不清晰可以看看这个视频。
