单调栈 （Monotonic Stack）是一种维护「元素值在原数组中的索引」的栈结构，其对应的元素值满足单调递增或递减.它通常用于解决寻找下一个更大/更小元素或寻找最近更大/更小元素等问题。

[!NOTE] insight
当来了一个元素，判断栈是否为空，如果为空，则直接将索引放进去；
否则将栈中索引对应数组值破坏单调性的索引，都弹出，再将当前元素索引放入；
那些弹出元素都等到了比他们大/小的元素，这个元素就是刚刚迫使它们弹出的那个元素！

注意是索引！！！

其中栈内元素保持单调递增或单调递减的索引！！

保存索引，既能在O（1）恢复值，又能保存索引；如果保存值，无法保存索引

1. 核心特征

栈内所有元素，都在等待那个比它大/小的元素（即单调栈的用途：寻找下一个更大/更小元素）

维护一组对应原数组上值单调的元素（通常保存这些元素的索引）

  1. 单调性：

    • 递增栈：从栈底到栈顶递增
    • 递减栈：从栈底到栈顶递减

  2. 维护方式：

    • 入栈前，将破坏单调性的栈顶元素都弹出
    • 新元素入栈

2. 常见应用场景

2.1 下一个更大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def nextGreaterElement(nums):
    n = len(nums)
    result = [-1] * n  # 默认值为-1
    stack = []  # 递减栈
    
    # 从左向右遍历
    for i in range(n):
        # 当前元素比栈顶元素大，说明找到了栈顶元素的下一个更大元素
        while stack and nums[i] > nums[stack[-1]]:
            prev_index = stack.pop()
            result[prev_index] = nums[i]
        stack.append(i)
    
    return result

# 示例
nums = [2, 1, 2, 4, 3]
print(nextGreaterElement(nums))  # [4, 2, 4, -1, -1]

模拟：

1
2
3
4
2->[0]
1->[0,1]
2->[0,2]  i = 2,stack = [0,1],nums[stack[-1]] = nums[1]= 1, 2>1,弹出1，result[1] = nums[2] = 2
4->[]

2.2 直方图中最大矩形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def largestRectangleArea(heights):
    stack = []  # 递增栈
    max_area = 0
    heights = heights + [0]  # 添加哨兵
    
    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i - (stack[-1] + 1 if stack else 0)
            max_area = max(max_area, height * width)
        stack.append(i)
    
    return max_area

# 示例
heights = [2, 1, 5, 6, 2, 3]
print(largestRectangleArea(heights))  # 10

3. 常见模式

3.1 递增栈模式

1
2
3
4
5
6
7
def increasingStack(nums):
    stack = []  # 递增栈
    for num in nums:
        # 保持栈的递增性
        while stack and stack[-1] > num:
            stack.pop()
        stack.append(num)

3.2 递减栈模式

1
2
3
4
5
6
7
def decreasingStack(nums):
    stack = []  # 递减栈
    for num in nums:
        # 保持栈的递减性
        while stack and stack[-1] < num:
            stack.pop()
        stack.append(num)

4. 实际应用示例

4.1 温度问题（每日温度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dailyTemperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # 存储索引的递减栈
    
    for i, temp in enumerate(temperatures):
        while stack and temp > temperatures[stack[-1]]:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day
        stack.append(i)
    
    return result

# 示例
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

4.2 环形数组中下一个更大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # 递减栈
    
    # 遍历两次数组
    for i in range(n * 2):
        index = i % n
        while stack and nums[index] > nums[stack[-1]]:
            result[stack.pop()] = nums[index]
        if i < n:  # 只在第一次遍历时入栈
            stack.append(index)
    
    return result

# 示例
nums = [1, 2, 1]
print(nextGreaterElements(nums))  # [2, -1, 2]

5. 性能特征

  1. 时间复杂度：

    • 通常为 O(n)，因为每个元素最多入栈和出栈一次

  2. 空间复杂度：

    • O(n)，用于存储栈

6. 使用技巧

  1. 选择栈的类型：

    • 找下一个更大元素：用递减栈
    • 找下一个更小元素：用递增栈

  2. 处理循环数组：

    • 遍历两次数组
    • 使用模运算处理索引

  3. 处理边界情况：

    • 添加哨兵元素
    • 初始化结果数组

7. 总结

单调栈的核心优势是：

  1. 可以在线性时间内解决”下一个更大/更小元素”类问题
  2. 实现简单，思路清晰
  3. 适用于需要维护某种单调性的场景

使用单调栈时需要注意：

  1. 确定使用递增栈还是递减栈
  2. 是否需要存储元素索引
  3. 是否需要处理循环情况
  4. 初始值和边界条件的处理

掌握单调栈这个工具，对解决特定类型的问题非常有帮助。