单调栈和单调队列

算法概述

【单调栈】和【单调队列】是栈和队列的变种，它们在保持基本操作的同时，额外维护了元素的单调性：

• 单调栈：栈内元素始终保持单调递增或单调递减
• 单调队列：队列中的元素始终保持单调递增或单调递减

这两种数据结构在处理区间最值问题时特别高效。

单调栈

算法设计思路

单调栈的核心思想是：入栈时弹出违反单调性的元素，确保栈中元素始终满足单调性条件。常用于解决以下问题：

1. 寻找数组中每个元素的下一个更大/更小元素
2. 直方图中最大矩形面积
3. 区间内的最大值最小值等

代码实现与解析

// 以求解数组中每个元素的下一个更大元素为例
vector<int> nextGreaterElement(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[i] > nums[st.top()]) {
            int idx = st.top();
            st.pop();
            result[idx] = nums[i]; // nums[i]是nums[idx]的下一个更大元素
        }
        st.push(i); // 当前索引入栈
    }

    return result;
}

时间复杂度分析

• 时间复杂度：O(n)，虽然有两层循环，但每个元素最多入栈、出栈各一次
• 空间复杂度：O(n)，栈的大小

单调队列

算法设计思路

单调队列通常用于求解滑动窗口中的最大值或最小值问题。其核心思想是：

1. 入队时，从队尾开始，移除所有不满足单调性的元素
2. 出队时，如果队首元素是要出队的元素，则将其移除

代码实现与解析

// 以求解滑动窗口最大值为例
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // 双端队列存储元素索引，队首到队尾为递减顺序

    for (int i = 0; i < nums.size(); i++) {
        // 移除不在当前窗口的元素
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 从队尾移除小于当前元素的所有元素，保持单调递减
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i); // 当前索引入队

        // 当窗口大小达到k时，记录结果
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]); // 队首元素为当前窗口最大值
        }
    }

    return result;
}

时间复杂度分析

• 时间复杂度：O(n)，每个元素最多入队和出队一次
• 空间复杂度：O(k)，队列的大小不超过滑动窗口的大小

应用场景比较

典型例题分析

单调栈例题：接雨水问题

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

int trap(vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;

    int result = 0;
    stack<int> st; // 单调递减栈，存储索引

    for (int i = 0; i < n; i++) {
        // 当栈不为空且当前高度大于栈顶高度
        while (!st.empty() && height[i] > height[st.top()]) {
            int bottom = st.top();
            st.pop();

            if (st.empty()) break; // 左边没有边界，无法形成水槽

            // 计算宽度和高度
            int width = i - st.top() - 1;
            int h = min(height[st.top()], height[i]) - height[bottom];
            result += width * h; // 累加当前形成的水量
        }
        st.push(i);
    }

    return result;
}

单调队列例题：滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq;

    for (int i = 0; i < nums.size(); i++) {
        // 移除不在当前窗口的元素
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 维护单调递减队列
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // 当窗口大小达到k时，记录结果
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

易错点与调试技巧

1. 【单调性方向】根据问题选择正确的单调方向（递增或递减）

   // 求下一个较大元素用单调递减栈
   while (!st.empty() && nums[i] > nums[st.top()]) {...}
   
   // 求下一个较小元素用单调递增栈
   while (!st.empty() && nums[i] < nums[st.top()]) {...}
   

2. 【边界处理】特别是窗口大小关系和初始化问题

   // 注意滑动窗口最值问题中的窗口边界条件
   if (i >= k - 1) { // 当i从0开始时，i=k-1时窗口刚好形成完整窗口
       result.push_back(nums[dq.front()]);
   }
   

3. 【入队出队顺序】在处理单调队列时，先处理过期元素，再维护单调性

   // 错误顺序
   while (!dq.empty() && nums[dq.back()] < nums[i]) {
       dq.pop_back();
   }
   if (!dq.empty() && dq.front() <= i - k) { // 可能出现队列为空的错误判断
       dq.pop_front();
   }
   
   // 正确顺序
   if (!dq.empty() && dq.front() <= i - k) {
       dq.pop_front();
   }
   while (!dq.empty() && nums[dq.back()] < nums[i]) {
       dq.pop_back();
   }
   

优化与扩展

STL优化技巧

在C++中，使用deque实现单调队列更加高效，因为它支持两端快速插入和删除操作。

// C++中deque的使用技巧
deque<int> dq;
dq.push_back(value); // 从尾部添加元素
dq.pop_back();       // 从尾部删除元素
dq.push_front(value);// 从头部添加元素
dq.pop_front();      // 从头部删除元素
dq.front();          // 获取队列头部元素
dq.back();           // 获取队列尾部元素

应用扩展

单调栈和单调队列还可以解决以下问题：

• 最大矩形面积（单调栈）
• O(n)时间内求解股票买卖的最大收益（单调栈）
• 任意区间最值查询（单调队列 + 分块或线段树）

练习题推荐

1. LeetCode 42: 接雨水（单调栈）
2. LeetCode 84: 柱状图中最大的矩形（单调栈）
3. LeetCode 239: 滑动窗口最大值（单调队列）
4. LeetCode 739: 每日温度（单调栈）
5. LeetCode 901: 股票价格跨度（单调栈）

总结

单调栈和单调队列是处理特定问题时的强大工具，它们通过牺牲一部分通用性，换取了在特定场景下更高的性能。核心思想是通过维护数据结构的单调性，快速定位区间内的最值元素。在处理滑动窗口最值和"下一个更大/更小元素"等问题时，它们的时间复杂度优势尤为明显。