抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

算法-单调栈

算法

发布于：2025年4月9日

字数：2.2k 字

时长：8 分钟

前言

在算法设计的工具箱中，单调栈是一种优雅而强大的数据结构，它能够将某些看似复杂的问题简化为线性时间解决方案。单调栈的核心思想是维护栈内元素的单调性，通过这种特性，我们可以高效地解决”寻找下一个更大/更小元素”之类的问题。本文将深入剖析单调栈的原理、实现方法及其典型应用场景，并提供详细的代码示例和解题模板。

单调栈的基本概念

定义

单调栈是一种特殊的栈结构，它要求栈中元素保持单调递增或单调递减的顺序。根据要解决的问题类型，我们可以构建：

  • 单调递增栈：从栈底到栈顶元素单调递增，用于寻找下一个更小元素
  • 单调递减栈：从栈底到栈顶元素单调递减，用于寻找下一个更大元素

工作原理

单调栈的核心操作是在遍历数组的过程中维护栈的单调性：

  1. 遍历数组中的每个元素
  2. 将当前元素与栈顶元素比较
  3. 如果当前元素破坏了栈的单调性，则弹出栈顶元素，直到栈为空或不再破坏单调性
  4. 在弹出过程中，对于被弹出的元素，当前元素就是其”下一个更大/更小元素”
  5. 将当前元素入栈

每个元素最多入栈出栈各一次，因此时间复杂度为 $O(n)$。

单调栈的实现模板

寻找下一个更大元素模板（单调递减栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # 默认值为-1，表示没有更大的元素
    stack = []  # 存储元素的索引
    
    for i in range(n):
        # 当前元素大于栈顶元素时，更新结果
        while stack and nums[i] > nums[stack[-1]]:
            result[stack[-1]] = nums[i]  # 当前元素是栈顶元素的下一个更大元素
            stack.pop()
        stack.append(i)  # 将当前元素索引入栈
    
    return result

寻找下一个更小元素模板（单调递增栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
def next_smaller_element(nums):
    n = len(nums)
    result = [-1] * n  # 默认值为-1，表示没有更小的元素
    stack = []  # 存储元素的索引
    
    for i in range(n):
        # 当前元素小于栈顶元素时，更新结果
        while stack and nums[i] < nums[stack[-1]]:
            result[stack[-1]] = nums[i]  # 当前元素是栈顶元素的下一个更小元素
            stack.pop()
        stack.append(i)  # 将当前元素索引入栈
    
    return result

寻找前一个更大元素模板（单调递减栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
def prev_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # 默认值为-1，表示没有更大的元素
    stack = []  # 存储元素的索引
    
    for i in range(n-1, -1, -1):
        # 当前元素大于栈顶元素时，更新结果
        while stack and nums[i] > nums[stack[-1]]:
            result[stack[-1]] = nums[i]  # 当前元素是栈顶元素的前一个更大元素
            stack.pop()
        stack.append(i)  # 将当前元素索引入栈
    
    return result

寻找前一个更小元素模板（单调递增栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
def prev_smaller_element(nums):
    n = len(nums)
    result = [-1] * n  # 默认值为-1，表示没有更小的元素
    stack = []  # 存储元素的索引
    
    for i in range(n-1, -1, -1):
        # 当前元素小于栈顶元素时，更新结果
        while stack and nums[i] < nums[stack[-1]]:
            result[stack[-1]] = nums[i]  # 当前元素是栈顶元素的前一个更小元素
            stack.pop()
        stack.append(i)  # 将当前元素索引入栈
    
    return result

题解示例

力扣 496：下一个更大元素 I

问题描述：给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []
    
    # 构建nums2中每个元素的下一个更大元素映射
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack[-1]] = num
            stack.pop()
        stack.append(num)
    
    # 从映射中获取nums1中每个元素的答案
    result = []
    for num in nums1:
        result.append(next_greater.get(num, -1))
    
    return result

力扣 84：柱状图中最大的矩形

问题描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def largestRectangleArea(heights):
    n = len(heights)
    stack = []
    max_area = 0
    
    for i in range(n + 1):
        curr_height = 0 if i == n else heights[i]
        
        # 当栈不为空且当前高度小于栈顶高度时，计算面积
        while stack and curr_height < heights[stack[-1]]:
            height = heights[stack.pop()]
            
            # 计算宽度
            width = i if not stack else i - stack[-1] - 1
            
            # 更新最大面积
            max_area = max(max_area, height * width)
        
        stack.append(i)
    
    return max_area

力扣 42：接雨水

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

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def trap(height):
    n = len(height)
    result = 0
    stack = []
    
    for i in range(n):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            
            if not stack:
                break
            
            # 计算宽度和高度
            width = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            
            # 累加接水量
            result += width * bounded_height
        
        stack.append(i)
    
    return result

力扣 739：每日温度

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

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 存储索引
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)
    
    return answer

单调栈的应用思路

单调栈适用的问题

单调栈通常适用于解决以下类型的问题：

  1. 寻找数组中每个元素的下一个或前一个更大/更小元素
  2. 涉及到区间最值的问题
  3. 需要高效计算区间内满足特定条件的元素

解题思路

应用单调栈解决问题的一般步骤：

  1. 明确维护的单调性：根据问题需要决定使用递增栈还是递减栈
  2. 确定存储内容：栈中存储元素值还是索引（通常存储索引更灵活）
  3. 遍历方向：正向遍历通常用于找下一个元素，反向遍历通常用于找前一个元素
  4. 处理循环数组：如果是循环数组，可以通过数组拼接或模运算处理

常见变形与技巧

  1. 双向单调栈：同时维护前一个和后一个更大/更小元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_both_adjacent_greater(nums):
    n = len(nums)
    next_greater = [-1] * n
    prev_greater = [-1] * n
    
    # 找下一个更大元素
    stack = []
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            next_greater[stack[-1]] = nums[i]
            stack.pop()
        stack.append(i)
    
    # 找前一个更大元素
    stack = []
    for i in range(n-1, -1, -1):
        while stack and nums[i] > nums[stack[-1]]:
            prev_greater[stack[-1]] = nums[i]
            stack.pop()
        stack.append(i)
    
    return next_greater, prev_greater
  1. 处理循环数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def next_greater_element_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # 遍历两次数组
    for i in range(n * 2):
        idx = i % n
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack[-1]] = nums[idx]
            stack.pop()
        
        # 只在第一次遍历时入栈
        if i < n:
            stack.append(idx)
    
    return result
  1. 结合其他数据结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def max_value_in_sliding_window(nums, k):
    n = len(nums)
    result = []
    # 使用双端队列实现单调递减队列
    deque = []
    
    for i in range(n):
        # 保持队列头部是当前窗口内的元素
        while deque and deque[0] < i - k + 1:
            deque.pop(0)
        
        # 维护单调递减性质
        while deque and nums[i] > nums[deque[-1]]:
            deque.pop()
        
        deque.append(i)
        
        # 当窗口形成后，记录结果
        if i >= k - 1:
            result.append(nums[deque[0]])
    
    return result

后记

单调栈作为一种特殊的数据结构，在解决序列中元素间关系的问题时展现出了惊人的效率。它的核心优势在于将原本需要 $O(n²)$ 时间复杂度的暴力解法优化到 $O(n)$，同时代码实现相对简洁。

Python作为一种高级语言，实现单调栈算法时代码更加简洁明了，但核心思想不变。通过使用Python内置的列表作为栈，我们可以快速实现各种单调栈的应用。

掌握单调栈不仅需要理解其工作原理，更重要的是培养识别适用问题的敏感度。通过本文提供的模板和示例，相信读者能够快速上手并灵活应用单调栈解决各类问题。

在算法学习的道路上，单调栈是一个不可或缺的工具，它的思想体现了”以空间换时间”的经典策略，值得每位算法爱好者深入研究和掌握。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/30749c48/

更新于：2025年4月9日

单调栈

评论