单调栈

结构特性

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

适用场景

如果要在一个非负整数数组里求解某个整数左右边界（即左右两边第一个小于当前元素值的元素），一般情况下需要不断向左右两边遍历查找，是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

相关题目

接雨水