Python 数据结构基础（二）：单调栈

1. 单调栈的定义

单调栈（Monotone Stack）：一种特殊的栈。在栈的先进后出规则基础上，要求从栈顶到栈底的元素是单调递增（或者单调递减）。其中，满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。

2. 单调栈的基本操作

单调栈的基本操作和普通栈的基本操作类似，只是在入栈和出栈的过程中需要满足单调栈的性质。

3. 单调栈的应用场景

单调栈可以在时间复杂度为 O(n) 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。所以单调栈一般用于解决一下几种问题：

寻找左侧第一个比当前元素大的元素。
寻找左侧第一个比当前元素小的元素。
寻找右侧第一个比当前元素大的元素。
寻找右侧第一个比当前元素小的元素。

无论哪种题型，都建议从左到右遍历元素。查找比当前元素大的元素就用单调递增栈，查找比当前元素小的元素就用单调递减栈。

3.1 单调递增栈

def monotoneIncreasingStack(nums: List[int]):
    """单调递增栈"""
    stack = []
    for num in nums:
        while stack and num >= stack[-1]:
            stack.pop()
        stack.append(num)

3.2 单调递减栈

def monotoneDecreasingStack(nums: List[int]):
    """单调递减栈"""
    stack = []
    for num in nums:
        while stack and num <= stack[-1]:
            stack.pop()
        stack.append(num)

4. 单调栈的练习

4.1 下一个更大元素

描述： nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中 nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

要求： 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例：

>>> nums1 = [4,1,2]
>>> nums2 = [1,3,4,2]
>>> ans = nextGreaterElement(nums1, nums2)
>>> print(ans)
[-1, 3, -1]

代码：

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    """下一个更大元素"""
    stack = []
    # 哈希表，存储每个元素对应的 “下一个更大元素”。
    next_greater = {}

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # 栈中剩余元素没有下一个更大元素，映射为-1
    for num in stack:
        next_greater[num] = -1

    # 构建结果数组
    ans = [next_greater[num] for num in nums1]

    return ans

4.2 每日温度

描述： 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 ans ，其中 ans[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例：

>>> temperatures = [73,74,75,71,69,72,76,73]
>>> ans = dailyTemperatures(temperatures)
>>> print(ans)
[1, 1, 4, 2, 1, 1, 0, 0]

代码：

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    """每日温度"""
    stack = []
    ans = [0] * len(temperatures)

    for i in range(len(temperatures)):
        # 当前温度比栈顶高，说明栈顶元素的下一个高温就是 i
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            ans[prev_index] = i - prev_index
        stack.append(i)

    return ans