OI 必学：单调栈与单调队列

零、背景

在 OI 比赛中，经常会遇到各种区间查询的问题。
如果能结合单调栈或者单调队列，往往可以把复杂度从朴素的 O(n^2) 降到 O(n) 或 O(n log n)。

下面简单介绍这两个数据结构的概念、常见应用场景，以及一份可复用的模板代码。

一、单调栈

单调栈，指栈内元素从栈底到栈顶满足某种单调性（单调递增或单调递减）的栈。
在区间查询类问题中，我们更常用单调递减栈或单调递增栈来维护一段前缀上的极值信息。

比如求带离线询问的区间最大值问题，可以按右端点排序所有询问，然后依次处理。
在遍历数组时，从左到右依次把元素压入单调递减栈，当栈顶元素的位置等于当前询问的右端点时，就可以利用栈内的信息回答这个询问。

为什么单调栈能做到这一点呢？
设询问区间为 [l, r]，如果存在下标 i < j <= r，且 a[i] < a[j]，那么 a[i] 就不可能成为区间 [l, r] 的最大值。
也就是说，这类「明显不可能成为答案」的元素，可以在维护栈的时候被弹出，从而只保留对当前和未来区间仍然有价值的元素。

这样，我们就得到了一个关于 [1, r] 所有候选最大值的单调递减栈。
此时区间 [l, r] 的答案，就是栈中下标不小于 l 的元素中，最靠近栈顶的那个。
由于栈是单调的，也可以对栈做一次二分查找，加速定位答案。

实际做题时，一道题可能会同时用到多个单调栈，因此把其封装为一个结构体（或类）会更方便复用代码。
一般可以封装如下几个常用操作：

• push：入栈
• pop：出栈
• top：返回栈顶元素
• empty：判断栈是否为空
• size：返回栈中元素个数
• clear：清空栈

// 单调递减栈，栈顶是最小值
struct MonoStackMax {
  int idx[max4];
  ll val[max4];
  int l, r;
  inline void clear() { l = 0, r = 0; }
  inline void push(ll v, int pos) {
    while (l < r && val[r - 1] <= v) r--;
    val[r] = v;
    idx[r] = pos;
    r++;
  }
  inline void pop(int pos) {
    while (l < r && idx[r - 1] < pos) r--;
  }
  inline ll top() { return val[r - 1]; }
  inline bool empty() { return l == r; }
  inline int size() { return r - l; }
};

二、单调队列

单调队列与单调栈类似，只不过它维护的是一个满足单调性的队列。
它最典型的应用场景，就是解决固定区间长度的滑动窗口问题。

比如某道题要求：给定数组，求出所有长度为 K 的区间的最大值。
如果暴力去算，每个区间都扫描一遍，复杂度是 O(n * k)，在数据范围稍大时就会超时。

观察相邻两个区间 [i, i + k - 1] 和 [i + 1, i + k]，可以发现前一个区间只是在左端删除一个元素，后一个区间只是在右端插入一个元素。
如果删除的元素 a[i] 不是区间 [i, i + k - 1] 的最大值，那么这个元素对后续任何区间都没有影响，也就没必要继续存下来。
真正有影响的情况，是删除的元素 a[i] 恰好是当前区间的最大值。

因此，我们维护一个关于当前窗口 [i, i + k - 1] 的单调递减队列，队首始终是当前窗口的最大值所在位置。
当要求下一个窗口 [i + 1, i + k] 的最大值时，只需要把位置在窗口左端点左侧的元素从队列中「删除」，再将新加入的元素 a[i + k] 插入队列即可。
注意，如果 a[i] 本就不是最大值，它根本不会出现在队列里，自然也不需要显式删除。

为了方便处理这种「按位置删除」的需求，我们通常会把元素的位置也一起存下来，删除时基于下标来判断，而不是简单地从队头直接出队一次。
和单调栈类似，单调队列的常用操作也可以封装成一个结构体（或类）。

// 单调递减队列，队首是最大值
struct MonoQueueMax {
  int idx[max4];
  ll val[max4];
  int l, r;
  inline void clear() { l = 0, r = 0; }
  inline void push(ll v, int pos) {
    while (l < r && val[r - 1] <= v) r--;
    val[r] = v;
    idx[r] = pos;
    r++;
  }
  inline void pop(int pos) {
    while (l < r && idx[l] < pos) l++;
  }
  inline ll top() { return val[l]; }
  inline bool empty() { return l == r; }
  inline int size() { return r - l; }
};

三、总结

单调栈和单调队列的核心思想，都是「用单调性丢掉不可能成为答案的元素，只保留对当前和未来区间仍有贡献的那些」。
单调栈多用于一些需要从一侧「扫过去」并维护前缀信息的问题；单调队列则尤其适合处理固定长度滑动窗口的极值查询。
掌握这两个数据结构的思想和模板，很多原来看起来需要 O(n * k) 的暴力做法，都可以优化到 O(n) 级别。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code