一、算法概述

单调栈和单调队列是两种维护元素单调性的线性数据结构技巧。它们通过在元素进出时弹出破坏单调性的元素，从而在 O(n) 时间内解决一系列"找下一个更大/更小元素"和"滑动窗口最值"类问题。

  • 单调栈：栈中元素保持单调递增或单调递减，常用于找每个元素左右两侧第一个比它大/小的元素
  • 单调队列：双端队列中元素保持单调性，队头维护当前窗口的最值，常用于滑动窗口问题

二、核心思想

2.1 单调栈

核心规则：在将元素压入栈之前，先弹出栈中所有破坏单调性的元素。

以单调递减栈（找下一个更大元素）为例：

  • 从左到右遍历数组
  • 当前元素 x 入栈前，不断弹出栈中比 x 小的元素
  • 这些被弹出的元素，它们的下一个更大元素就是 x

为什么是 O(n)？ 每个元素最多入栈一次、出栈一次，总操作 2n 次。

2.2 单调队列

核心规则：用双端队列维护一个滑动窗口，队尾保持单调性，队头判断过期。

以滑动窗口最大值为例：

  • 队列中存储元素下标（方便判断是否过期），且对应值保持单调递减
  • 新元素入队时，从队尾弹出所有比它小的元素
  • 队头元素若下标超出窗口范围（i - k + 1），则弹出
  • 当前窗口的答案即为队头元素

为什么是 O(n)？ 每个元素最多入队一次、出队一次，总操作 2n 次。

三、算法步骤 / 伪代码

单调栈 —— 下一个更大元素

function nextGreaterElement(nums):
    n = length(nums)
    result = array of size n, default -1
    stack = empty stack  // 存储下标，保持对应值单调递减
    
    for i from 0 to n-1:
        while stack not empty and nums[stack.top()] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.push(i)
    
    return result

单调队列 —— 滑动窗口最大值

function maxSlidingWindow(nums, k):
    n = length(nums)
    result = empty array
    deque = empty double-ended queue  // 存储下标，值单调递减
    
    for i from 0 to n-1:
        // 1. 移除过期元素（队头下标超出窗口）
        while deque not empty and deque.front() <= i - k:
            deque.pop_front()
        
        // 2. 维护单调性（从队尾弹出小于当前值的元素）
        while deque not empty and nums[deque.back()] < nums[i]:
            deque.pop_back()
        
        // 3. 当前元素入队
        deque.push_back(i)
        
        // 4. 记录窗口最大值（窗口形成后）
        if i >= k - 1:
            result.push_back(nums[deque.front()])
    
    return result

四、C++ 代码实现

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
using namespace std;

// ==================== 1. 单调栈 ====================

// 下一个更大元素（Next Greater Element）
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);   // 默认 -1 表示不存在
    stack<int> st;               // 存储下标，对应值保持单调递减

    for (int i = 0; i < n; i++) {
        // 栈中比当前元素小的元素，它们的"下一个更大元素"就是当前元素
        while (!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

// 下一个更小元素（Next Smaller Element）
vector<int> nextSmallerElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;  // 对应值保持单调递增

    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] > nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

// 上一个更大元素（Previous Greater Element）
vector<int> prevGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;  // 单调递减

    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] <= nums[i]) {
            st.pop();
        }
        result[i] = st.empty() ? -1 : nums[st.top()];
        st.push(i);
    }
    return result;
}

// ==================== 2. 单调队列 ====================

// 滑动窗口最大值
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    deque<int> dq;  // 存储下标，对应值保持单调递减

    for (int i = 0; i < n; i++) {
        // 1. 移除过期元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 2. 维护单调性：队尾弹出所有小于当前值的元素
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 3. 当前元素入队
        dq.push_back(i);

        // 4. 窗口形成后记录答案
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

// 滑动窗口最小值
vector<int> minSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    deque<int> dq;  // 存储下标，对应值保持单调递增

    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 维护单调递增：弹出大于当前值的元素
        while (!dq.empty() && nums[dq.back()] > nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

// ==================== 辅助函数 ====================
void printVector(const vector<int>& vec, const string& label) {
    cout << label << ": ";
    for (int v : vec) cout << v << " ";
    cout << endl;
}

// ==================== 测试主函数 ====================
int main() {
    // ---------- 单调栈测试 ----------
    cout << "==================== 单调栈测试 ====================" << endl;

    // 测试1：下一个更大元素
    vector<int> nums1 = {2, 1, 2, 4, 3};
    printVector(nums1, "原数组");
    vector<int> nge = nextGreaterElement(nums1);
    printVector(nge, "下一个更大元素   ");
    // 期望: 4 2 4 -1 -1

    // 测试2：下一个更小元素
    vector<int> nse = nextSmallerElement(nums1);
    printVector(nse, "下一个更小元素   ");
    // 期望: 1 -1 -1 3 -1

    // 测试3：上一个更大元素
    vector<int> pge = prevGreaterElement(nums1);
    printVector(pge, "上一个更大元素   ");
    // 期望: -1 2 2 -1 4

    // 测试4：LeetCode 739 每日温度
    cout << "\n--- LeetCode 739: 每日温度 ---" << endl;
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    printVector(temperatures, "温度数组");
    int n = temperatures.size();
    vector<int> answer(n, 0);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
            int idx = st.top(); st.pop();
            answer[idx] = i - idx;
        }
        st.push(i);
    }
    printVector(answer, "等待天数        ");
    // 期望: 1 1 4 2 1 1 0 0

    // ---------- 单调队列测试 ----------
    cout << "\n==================== 单调队列测试 ====================" << endl;

    // 测试5：滑动窗口最大值
    vector<int> nums2 = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    printVector(nums2, "原数组");
    cout << "窗口大小 k = " << k << endl;
    vector<int> maxWin = maxSlidingWindow(nums2, k);
    printVector(maxWin, "滑动窗口最大值  ");
    // 期望: 3 3 5 5 6 7

    // 测试6：滑动窗口最小值
    vector<int> minWin = minSlidingWindow(nums2, k);
    printVector(minWin, "滑动窗口最小值  ");
    // 期望: -1 -3 -3 -3 3 3

    // 测试7：另一组滑动窗口最大值
    cout << "\n--- 附加示例 ---" << endl;
    vector<int> nums3 = {7, 2, 4};
    k = 2;
    printVector(nums3, "原数组");
    maxWin = maxSlidingWindow(nums3, k);
    printVector(maxWin, "滑动窗口最大值  ");
    // 期望: 7 4

    return 0;
}

五、复杂度分析

单调栈

操作 时间复杂度 说明
全体入栈 O(n) 每个元素最多入栈一次
全体出栈 每个元素最多出栈一次
总复杂度 O(n) 均摊 O(1) 每元素
空间复杂度 O(n) 栈中最多同时存储 n 个元素

单调队列

操作 时间复杂度 说明
全体入队 O(n) 每个元素最多入队一次
全体出队（过期+维护） 每个元素最多出队一次
总复杂度 O(n) 均摊 O(1) 每元素
空间复杂度 O(k) 最多存储窗口大小 k 个元素

为什么是 O(n)？

两种数据结构的核心分析方法一致：均摊分析。虽然内层有 while 循环，但每个元素在整个过程中最多被弹出一次，所有弹出操作的总次数不超过 n。因此总复杂度为 O(n)。

六、应用场景

单调栈

场景 说明
下一个更大/更小元素 Next Greater / Smaller Element 系列问题
每日温度 求距下一次更高温度的天数
接雨水 用单调递减栈找左右两侧更高的柱子
柱状图中的最大矩形 找每个柱子左右两侧第一个更矮的柱子
132 模式 单调栈维护候选的 "3" 和 "2"
股票价格跨度 求连续不大于当天的天数

单调队列

场景 说明
滑动窗口最值 滑动窗口最大值/最小值
带限制的 DP 优化 单调队列优化 DP（如多重背包、最大子序和）
环形数组问题 破环成链后使用滑动窗口
跳跃游戏 求能到达的最远位置或最小跳跃次数

七、经典例题

7.1 LeetCode 739 - 每日温度

题目：给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果之后都不会升高，answer[i] = 0。

解题思路：经典单调栈。从左到右遍历，维护一个单调递减栈（存储下标）。当 temperatures[i] > temperatures[st.top()] 时，栈顶元素找到了下一个更高温度的天数 i - st.top()。

见本文 "LeetCode 739: 每日温度" 测试代码部分。

7.2 LeetCode 239 - 滑动窗口最大值

题目：给定一个整数数组 nums 和一个大小为 k 的滑动窗口，窗口从数组的最左端移动到最右端。每次窗口向右滑动一位，返回每个窗口中的最大值。

解题思路：经典单调队列。用双端队列维护窗口中元素的单调递减性。队头始终是当前窗口的最大值。入队时从队尾移除较小元素，并移除已滑出窗口的过期元素。

见本文 maxSlidingWindow 函数实现。

进一步练习：

  • LeetCode 42：接雨水（单调栈 / 双指针）
  • LeetCode 84：柱状图中最大的矩形（单调栈）
  • LeetCode 456：132 模式（单调栈）
  • LeetCode 862：和至少为 K 的最短子数组（单调队列 + 前缀和）
  • LeetCode 1696：跳跃游戏 VI（单调队列优化 DP）
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 33ms
  4. Powered by Hydro v5.0.1 Community