如果要在一个非负整数数组里求解某个整数左右边界(即左右两边第一个小于当前元素值的元素),一般情况下需要不断向左右两边遍历查找,是O(n^2)的时间复杂度。如果使用单调递增栈,则能缓存左边界的值,随着元素不断入栈,不满足递增特性的值即是右边界,时间复杂度为O(n)。
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以图中的柱图为例,我们要求位置为2高度为5的柱子所能构成的最大面积。其左边第一个高度小于5的柱子位置为1高度为1,右边第一个高度小于5的柱子位置4高度 2,假设heights表示柱子高度的数组,左右边界的位置分别是left和right,所以其最大面积为heights[2](right-left-1) = 5 (4-1-1) = 10
明确了计算的方法,我们就只差怎样确定柱子左右边界了。
利用单调递增栈的特性,对元素进行入栈操作,如果高度满足递增要求,则直接入栈,若柱子高度小于栈顶柱子高度,则该柱子为栈顶柱子的右边界,而栈顶柱子在栈内的左边第一个柱子为其左边界,此时就确定了两个边界了。
计算完栈顶柱子的最大面积,需要将其出栈,待入栈的柱子继续去新的栈顶柱子比较。
此时可能有读者想到,如果柱子高度的数组本来就是单调递增的,那就只是一直入栈,并没有出栈计算面积的时候。此时可以在柱子遍历完成后判断栈是否为空,不为空则强制出栈,此时右边界相当于是高度为0的柱子。
另外还有柱子高度的数组是单调递减的情况,即一直是出栈,栈顶找不到其栈内左边的元素。
为了简化编码流程,可以采用更巧妙的哨兵机制,即在原始柱子调度数组首尾加上0,即高度为0的柱子,即不影响面积的计算,又能兼容上述情况。
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = [0]+heights+[0]
stack = []
res = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
cur = stack.pop()
res = max(res, heights[cur]*(i-stack[-1]-1))
stack.append(i)
return res
感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/110.html
邮箱:glowrypauky@gmail.com
QQ: 892413924