单调栈与单调队列

单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，用于解决一些与单调性相关的问题。单调栈可以分为单调递增栈和单调递减栈两种类型。

单调递增栈：栈中元素保持单调递增的顺序，即栈底到栈顶元素依次增大。

单调递减栈：栈中元素保持单调递减的顺序，即栈底到栈顶元素依次减小。

单调栈常用于解决求解某个元素向左或向右第一个比它大或小的元素的位置或值的问题。在遍历数组或序列的过程中，利用单调栈可以有效地找到符合条件的元素。

例题：单调栈

题目描述

给定一个长度为 N 的整数数组 f[N]，对于每一个数，请你输出这个数左边第一个小于它的数，如果不存在则输出 −1.

输入格式

第一行 输入一个数字 n，表示数组长度。

第二行 输入 n 个数字。

数据范围：1≤n≤105，1≤f[i]≤109

输出格式

共一行，包含 n 个数字，其中第i个表示第i个数左边第一个比它小的数，不存在输出 −1

输入样例

6
3 7 5 4 2 9

输出样例

-1 3 3 3 -1 2

题目分析

首先考虑暴力做法，外层循环 i 枚举每个数，内层 j 从 i−1 开始往左边找第一个小于 i 的数，时间复杂度 O(n2)。

假设当前枚举到 i，考虑 1∼i−1 的所有数，若存在两个数 a[j] > a[k] && j < k 则数 a[j] 用于不会被作为答案输出， 对于 1∼i−1 间的所有数，我们可以用一个栈来存储，并把永远不会作为答案输出的值从栈里面去掉，这样我们维护的栈一定是单调递增的，对任意一个 a[i]，只需要往栈顶往下找满足条件的数即可，并同时把不满足条件（≥a[i]）的数剔除掉，最后将 a[i] 也压入栈中。

示例代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int stk[N], tt;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i++) {
        while (stk[tt] >= a[i]) tt--;  // 若栈顶元素>=a[i],出栈
        if (tt == 0) cout << "-1 ";   // 栈为空，表示没有比我小的数
        else cout << stk[tt] << " ";  // 否则栈顶元素就是满足的结果
        stk[++tt] = a[i];             // 当前元素入栈
    }
    return 0;
}

单调队列

单调队列（Monotonic Queue）是一种特殊的队列结构，它具有保持队列元素单调性（单调递增或单调递减）的特点。单调队列通常用于解决一些与滑动窗口相关的问题，例如找出滑动窗口中的最大值或最小值。

单调队列的特性在于，队列中的元素按照一定的顺序排列，使得在滑动窗口移动的过程中，能够高效地维护当前窗口内的最值，并且能够在O(1)时间内获取到最值。

具体实现单调队列的方法有多种，常见的是利用双端队列（Deque）结构来实现。在向队列中添加元素时，保持队列的单调性，即在保持单调递增（或单调递减）的情况下，添加元素；而在队列中存在破坏单调性的元素时，则将其移除。

单调队列的应用场景包括 滑动窗口最大值、滑动窗口最小值、滑动窗口中位数 等问题，在这些问题中，单调队列能够提供高效的解决方案。

例题：滑动窗口

题目描述

给定一个长度为 n 的数组。有一个大小为 k 的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的 k 个数字。窗口每次向右滑动一个数字的距离。

下面是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7], k = 3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

输入格式

输入包括两行。

第一行包括 n 和 k，分别表示数组的长度和窗口的大小。

第二行包括 n 个数字。

数据范围：1≤n≤106，1≤k≤n，数字大小不超过 109。

输出格式

输出包括两行。

第一行包括窗口从左至右移动的每个位置的最小值。

第二行包括窗口从左至右移动的每个位置的最大值。

输入样例

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

题目分析

以找滑动窗口内的最大值为例，我们需要解决的就两个问题：

  1. 维护一个大小为 k 的滑动窗口。
  2. 找出当前窗口里的最大值。

首先第一个问题很容易实现，只要在这个元素入队前，计算下当前队列里的元素数量，如果到了 k 就把队头出队即可。

而第二个问题，容易想到直接遍历一遍队列找最大值，但这样操作时间复杂度为 O(k)，显然会超时。

试想一下，按当前方式维护的滑动窗口，里面是有大量无用的数据的。什么叫无用的数据呢？对于该题，就是不可能成为答案的数据，这里要实现的功能是找最大值，那么当当前元素入队的时候，前面所有比它小的元素必然不可能再作为答案了，因为当前元素不管是从大小、还是从“存活”时间来说，都是比前面这些元素要强的。

也就意味着，每次新元素入队前，可以把前面所有比它小的元素出队，经过这样操作，会发现，队列里面始终保持着单调递减的性质，所以每个滑动窗口的最大值就是当前的队首元素。这便是单调队列的妙用。

至于时间复杂度，队列只会把每个元素访问一遍，所以复杂度为 O(n) 。

那么同理，滑动窗口最小值也可以依照上面的方式来实现。

示例代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N], q[N], hh, tt = -1; // q队列为双端队列，且存的是下标
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (int i = 0; i < n; i++) {
        while (hh <= tt && i - k + 1 > q[hh]) hh++;  // 维护窗口大小
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;  // 入队且维护单调性
        q[++tt] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]); // 判断符合窗口大小才输出
    }
    printf("\n");
    hh = 0, tt = -1;  // 重新初始化队头队尾
    for (int i = 0; i < n; i++) {
        while (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    return 0;
}