算法现学现卖—— 单调栈

作者:杨润炜
日期:2020/5/30 19:40

单调栈

结构特性

  • 先入后出
  • 入栈的数据满足单调递增或递减

适用场景

如果要在一个非负整数数组里求解某个整数左右边界(即左右两边第一个小于当前元素值的元素),一般情况下需要不断向左右两边遍历查找,是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的柱子,即不影响面积的计算,又能兼容上述情况。

代码实现

  1. class Solution:
  2. def largestRectangleArea(self, heights: List[int]) -> int:
  3. heights = [0]+heights+[0]
  4. stack = []
  5. res = 0
  6. for i in range(len(heights)):
  7. while stack and heights[stack[-1]] > heights[i]:
  8. cur = stack.pop()
  9. res = max(res, heights[cur]*(i-stack[-1]-1))
  10. stack.append(i)
  11. return res

相关题目

接雨水

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/110.html
邮箱:glowrypauky@gmail.com
QQ: 892413924