1.单调栈

指栈内元素保持单调性的栈结构，分为单调增栈（栈底到栈顶元素递增）和单调减栈（栈底到栈顶元素递减）

2.单调栈的特点

单调栈的单调需要我们主动维护。当出现一个要入栈的元素ele破坏栈的单调性时，元素ele先hold住暂时不入栈，不断pop栈顶元素，直到ele入栈不会破坏栈的单调性时才将ele入栈

代码范式(以递增栈为例)：

stack = []
for ele in eles:
    # 如果ele会改变单调性，则需要不断pop栈顶元素
    while stack and stack[-1] > ele:
        p = stack.pop()
    stack.append(ele)

3.单调栈解决的问题

从对单调栈特点的分析和代码范式中我们可以看到，只要遇到影响单调性的情况，就会产生出栈行为。换句话说，对于递增栈的栈顶元素，一旦它们遇到比自己小的元素，就会出栈

因此，单调栈适合解决的是【next greater element】 或者【 next smaller element】问题

关于什么是【next greater element】 或者【 next smaller element】，看下面的第一个例题

4.例

1.leetcode#### 739. 每日温度

请根据每日 气温 列表，重新生成一个列表，对应位置的输出是需要再等待多少天才能等到一个更高的气温。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

分析：这就是典型的next greater element问题 -> 等待多少天才能等到一个更高的气温。next greater element问题，就用递减栈，这样才能在meet next greater element时发生出栈并计算结果

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
# 维护一个存储下标的单调减栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。
# 如果一个下标在单调栈里，则【表示尚未找到下一次温度更高的下标】。

# 套用范式。
# 比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]，如果 T[i] > T[prevIndex]，则将 prevIndex 出栈，并将 prevIndex 对应的等待天数赋为 i - prevIndex。
# 重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

        stack = list()
        t_length = len(T)
        res_list = [0 for _ in range(t_length)]
        # 维护一个递减栈
        for key, value in enumerate(T):     
            while stack and T[stack[-1]] < value:
                res_list[stack[-1]] = key - stack[-1]
                stack.pop()
            stack.append(key)
        return res_list

2. leetcode#### 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

分析：显然，洼地才能装水，即形如[1,0,1]这样的柱子组合，两边高中间低才能装水。那么怎么和next greater/smaller element联系起来呢？当后面的柱子比前面低时，无法接雨水；而一旦找到一根比前面高的柱子，就可以接水并且可以计算。-> 这也就是next greater element问题。考虑使用递减栈

class Solution:
    def trap(self, height: List[int]) -> int:
        # 维护一个单调减栈
        # 遇到新元素大于stack[-1]，说明可以洼地，不断pop栈顶和结算，直到新元素小于栈顶，然后新元素入栈

        stack = []
        res = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                p = stack.pop()
                if not stack: break
                bottom = height[p]
                # 高度差 * 底
                res += (min(height[i], height[stack[-1]])-bottom) * (i-stack[-1]-1)
            stack.append(i)
        return res

3. leetcode#### 84. 柱状图中最大的矩形

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

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

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 和接雨水的题很像，按照单调栈的思路思考一下
        # 直觉上是递增栈，遇到更小元素的时候开始pop和结算

        # 对于一个高度，如果能得到向左和向右的边界
        # 那么就能对每个高度求一次面积
        # 遍历所有高度，即可得出最大面积
        # 【向左和向右的边界，就是找元素两边第一个小于本身的值】
        # 因此小于时要发生出栈，故使用递增栈，验证直觉猜想

        # tips, heights两端补0
        heights = [0] + heights + [0]
        stack = []
        l = len(heights)
        res = 0
        for i in range(l):
            while stack and heights[stack[-1]] > heights[i]:
                index = stack.pop()
                h = heights[index]
                temp_res = (i-stack[-1]-1)*h
                print(temp_res)
                res = max(res, temp_res)
            stack.append(i)
        return res