单调队列与单调栈

单调栈与单调队列

• 左边第一个比它大的数
• 右边第一个比它小的数
• 某个区间内的最大值或最小值

如果每次都用循环去找，时间复杂度往往会达到 $O(n^2)$，效率较低。
单调栈 和 单调队列 正是为了解决这类问题而产生的高效数据结构。

单调队列是一种高效维护滑动窗口最值的特殊数据结构。它的核心思想在于，通过巧妙地排除无用数据，确保队列内的元素始终具备单调性。

在处理数据时，单调队列会动态地剔除那些永远不可能成为当前或未来窗口最值的元素。对于一个滑动窗口，新元素加入队列尾部时，它会从尾部开始，将所有比它小（对于求最大值而言）的旧元素移除。这种“淘汰机制”保证了队列头部始终是当前窗口的最大值，同时整个队列元素从头至尾呈递减排列。

它的最大优势在于其惊人的效率。虽然滑动窗口问题看似复杂，但每个元素最多入队和出队各一次，这使得算法能在 O(n) 的线性时间内解决问题，远优于暴力解法。除了经典的滑动窗口最大值，它还适用于解决一系列与局部最值相关的题目，是算法竞赛和面试中不可或缺的利器。

单调栈是一种通过维护栈内元素的单调性，来高效求解“下一个更大（或更小）元素”这类问题的数据结构。它的核心价值在于能够快速找到每个元素与其相邻特定值之间的关系。

在遍历数组时，我们依次将元素入栈。但在入栈前，会进行检查以确保栈的单调性不被破坏。以单调递增栈为例，如果新元素小于栈顶元素，我们就需要将栈顶元素不断弹出，直到满足条件。这个弹出的过程，恰恰就是解决问题的关键——对于被弹出的元素而言，这个导致它弹出的新元素，正是它寻找的“下一个更小（或更大）”的目标。

它的优势在于其极致的效率。每个元素仅入栈和出栈一次，因此时间复杂度可以优化到惊人的 O(n)。它将原本需要嵌套循环的暴力搜索过程，转化为一次线性的扫描。无论是寻找左右边界，还是寻找邻近的最值，单调栈都提供了一种清晰且高效的思维模式和实现模板。

---



1. 单调结构的基本思想



单调结构的核心思想是：



在数据结构中，元素按照某种“单调性”排列，从而保证高效查询。



根据使用的数据结构不同，分为：

• 单调栈（Monotonic Stack）
• 单调队列（Monotonic Queue）

它们都不是新的容器，而是 在栈或队列的基础上，加入单调性约束的使用方式。

---



2. 单调栈





2.1 单调栈的概念



单调栈 是一种满足栈内元素 单调递增或单调递减 的栈结构。

常见的两种形式为：

• 单调递增栈：栈底到栈顶元素递增
• 单调递减栈：栈底到栈顶元素递减

以 单调递减栈 为例，栈内元素满足：

$$ a_{1} \ge a_{2} \ge \dots \ge a_{k} $$

这表示：越靠近栈顶，元素越小。

---



2.2 单调栈的维护方式



以从左向右遍历数组为例，每访问一个新元素 $x$ 时：

• 当栈顶元素不满足单调性时，持续弹栈
• 直到满足单调性后，将 $x$ 入栈

例如维护一个 单调递增栈（用于找右边第一个更小的元素）：



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



这里通常 存的是下标而不是值，方便后续计算位置关系。

---



2.3 单调栈的数学含义



假设我们使用单调栈寻找 每个元素右侧第一个比它小的元素。

如果元素 $i$ 在遍历时被弹出栈，说明存在一个 $j i$，使得：

$$ a_j a_i $$

并且这是满足条件的 最近的 $j$。

因此，单调栈实际上是在高效地维护一种 最近更大 / 更小关系。

---



2.4 单调栈的常见应用



1. 右边第一个更大（小）的元素
2. 左边第一个更大（小）的元素
3. 直方图最大矩形
4. 区间贡献计算

例如，在区间贡献问题中，常需要计算：

$$ \text{贡献} = a_i \times \text{控制区间长度} $$

而控制区间的左右边界，正是由单调栈确定的。

---



3. 单调队列





3.1 单调队列的概念



单调队列 是一种满足队列中元素 单调递增或单调递减 的队列结构。

最典型的应用场景是：



滑动窗口最值问题



例如：在长度为 $k$ 的区间内，实时求最大值或最小值。

---



3.2 滑动窗口问题描述



给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，
对于每个区间：

$$ [i-k+1, i] $$

求该区间内的最大值或最小值。

如果直接遍历区间，时间复杂度为：

$$ O(nk) $$

当 $n$ 和 $k$ 较大时会超时。

---



3.3 单调队列的维护方式



以维护 区间最大值的单调递减队列 为例：



for(int i = 1; i <= n; i++){
    while(!q.empty() && a[q.back()] <= a[i]){
        q.pop_back();
    }
    q.push_back(i);

    if(q.front() <= i - k){
        q.pop_front();
    }

    if(i >= k){
        cout << a[q.front()] << endl;
    }
}



队列中的元素始终满足：

$$ a_{q_1} \ge a_{q_2} \ge \dots \ge a_{q_m} $$

队首元素始终是当前窗口的最大值。

---



3.4 单调队列的数学解释



在单调队列中：

• 队列下标始终保持在当前窗口范围内
• 队列内部值满足单调性

因此，对于任意窗口 $[l,r]$，队首元素对应的值满足：

$$ \max(a_l, a_{l+1}, \dots, a_r) = a_{q_{\text{front}}} $$

这使得每个元素 最多进队一次、出队一次。

---



总结



单调栈与单调队列本质上是：



利用单调性，减少无效比较，提高整体效率



• 单调栈解决的是 左右最近关系
• 单调队列解决的是 滑动窗口最值问题



对比项	单调栈	单调队列
结构基础	栈	队列
主要用途	最近更大/更小	区间最值
是否滑动	否	是
常见题型	边界、贡献	窗口问题



当你发现问题中出现以下关键词时，应立刻考虑单调结构：

• 最近
• 左右第一个
• 区间最值
• 滑动窗口