您现在的位置是：首页 > 大数据

当前栏目

深入浅出单调栈与单调队列

队列队列深入浅出单调

2023-09-27 14:19:49 时间

一、单调栈

所谓单调栈，就是指满足单调性的栈结构：

单调递增栈： 栈中元素从栈底到栈顶是递增的；
单调递减栈： 栈中元素从栈底到栈顶是递减的。

例如对于单调递增栈，向其中插入元素的时候，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素：

stack<int> stk;

void insert(int x) {
    while (!stk.empty() && stk.top() > x)  // 当stk.top() <= x时满足单调性
        stk.pop();
    stk.push(x);
}

单调栈可以用来在一个数组中寻找某一个元素左边（或右边）第一个大于（或小于或大于等于或小于等于）它的元素（或元素的下标）。

这句话看起来有些绕，接下来我们只考虑以下四种「基本情形」。

情形一：寻找一个数左边第一个小于它的数

给定一个长度为 $n\,(\leq 10^5)$ 的数组 $a$ ，输出每个数左边第一个比它小的数，如果不存在则输出 $- 1$ 。

传统的暴力做法是双重循环：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++) {
        bool flag = false;
        for (int j = i - 1; ~j; j--) {
            if (a[j] < a[i]) {
                flag = true;
                cout << a[j] << ' ';
                break;
            }
        }
        if (!flag) cout << -1 << ' ';
    }
    
    return 0;
}

然而这种做法的复杂度是 $O(n^2)$ ，利用单调栈，我们可以将复杂度降低至 $O (n)$ 。

在指针 $i$ 从左往右遍历的过程中，我们可以用一个栈来保存 $i$ 左边的所有元素（不包括 $i$ 指向的元素），下标越大的元素越接近栈顶，下标越小的元素越接近栈底。

每次我们访问栈顶，只要栈顶元素大于等于 $a [i]$ ，我们就将栈顶元素弹出，直至栈顶元素小于 $a [i]$ ，此时输出栈顶元素并将 $a [i]$ 压入栈中。由于栈中保存了 $i$ 左边的所有元素，所以只要有答案，则答案一定在栈中。

📃 对证明不感兴趣的读者可以跳过这部分
讲到这里，可能会有读者好奇，栈不是一直在弹出元素吗，万一先前就把答案弹出去了怎么办？这里我们可以从数学的角度进行证明。假设对于 $a [i]$ ，答案一定存在，即

$\exists\, 0\leq p<i,\quad \text{s.t.}\; \begin{cases} a[p]<a[i], \\ a[t]>a[p], \quad t= p+1,\cdots,i-1 \end{cases}$

对于第二个约束，假设有某个 $a[t]\leq a[p]$ ，那么可知 $a [t] < a [i]$ 并且 $a [t]$ 在 $a [p]$ 的右边，从而 $a [t]$ 才应该是答案，矛盾！

下面证明，当指针指向 $a [i]$ 时， $a [p]$ 一定存在于栈中。
当指针指向 $a [p]$ 时，这一轮循环结束后， $a [p]$ 会被压入栈中，所以我们从 $p + 1$ 开始考虑。事实上， $\forall t\in[p+1,i-1]$ ，当指针指向 $a [t]$ 时，无论栈怎么弹出元素，都不会弹出 $a [p]$ ，这是因为栈弹出元素的前提是栈顶元素 $\geq a[t]$ ，而 $a [p] < a [t]$ 所以不会被弹出，自然地，当指针指向 $a [i]$ 时， $a [p]$ 仍在栈中。

由于每个元素一定会被压入一次且至多弹出一次，因此操作次数至多是 $2 n$ ，故总时间复杂度为 $O (n)$ 。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack<int> stk;

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.empty() && stk.top() >= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(a[i]);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

📝 代码完全可以简化，之所以这么写是为了方便统一格式。

情形二：寻找一个数左边第一个小于它的数的下标

和情形一类似，只不过这里我们寻找的是下标，如果不存在则输出 $- 1$ 。

只需对栈做一点小小的修改就能应对情形二。注意到之前我们寻找的是元素所以让栈去保存元素，现在我们寻找下标，所以让栈去保存元素的下标就可以了。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack<int> stk;

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.empty() && a[stk.top()] >= a[i]) stk.pop();  // 仅有两处修改
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(i);  // 仅有两处修改
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

情形三：寻找一个数右边第一个大于它的数

之前我们是在一个数的左边去寻找，所以让栈去保存这个数左边的所有数，类似地，现在需要让栈去保存这个数右边的所有数。

考虑将数组翻转（实际上不可能翻转，而是倒序遍历），因此情形三变成了「寻找一个数左边第一个大于它的数」，于是归结为情形一。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack<int> stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = n - 1; ~i; i--) {
        while (!stk.empty() && stk.top() <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(a[i]);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

情形四：寻找一个数右边第一个大于它的数的下标

结合情形二和情形三即可得出。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], ans[N];

stack<int> stk;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = n - 1; ~i; i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i] = -1;
        stk.push(i);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << ' ';

    return 0;
}

不难发现，这四种情形只在第 $16, 17, 20$ 行不同，其余部分的代码均相同，据此可以总结出以下三点区别：

遍历顺序（以怎样的顺序遍历数组 $a$ ）；
比较方式（如何比较当前元素和栈顶元素）；
栈中存储的是什么（是元素本身还是元素的下标还是其他）。

二、单调栈的应用

2.1 单调栈模板题I

原题链接：AcWing 830. 单调栈

此题对应情形一，不再赘述，直接给出AC代码。

#include <bits/stdc++.h>

using namespace std;

stack<int> stk;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        while (!stk.empty() && stk.top() >= x) stk.pop();
        if (!stk.empty()) cout << stk.top() << ' ';
        else cout << -1 << ' ';
        stk.push(x);
    }

    return 0;
}

2.2 单调栈模板题II

原题链接：洛谷 P5788 【模板】单调栈

此题对应情形四，不再赘述，直接给出AC代码。

#include <bits/stdc++.h>

using namespace std;

const int N = 3e6 + 10;

int a[N], ans[N];
stack<int> stk;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = n; i; i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        stk.push(i);
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;
}

2.3 Bad Hair Day

原题链接：POJ 3250 Bad Hair Day

本题类似于情形四，但还是有些区别。

首先应当注意到以下几点：

每头牛只向右看；
每头牛只能看见比自己低的牛的头顶；
若两头牛一样高，则它们互相看不到对方的头顶。

这相当于对数组中的某个数，我们要在它的右边寻找第一个大于等于它的数的下标，知道下标后，我们就可以算出这头牛能够看到多少头牛的头顶了。当然，如果找不到这样的数，说明这头牛的右边全是比它低的牛，此时用牛的数量减去该牛的下标（从 $1$ 开始）就是该牛能够看到的头顶的数量。

还需注意一个问题，假设给定的序列是单调递减的，那么所求答案为 $N(N-1)/2\approx 3\times 10^9$ ，会爆 int。

#include <stack>

using namespace std;

typedef long long LL;

LL h[80010], ans;
stack<LL> stk;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);

    for (int i = n; i; i--) {
        while (!stk.empty() && h[stk.top()] < h[i]) stk.pop();
        if (!stk.empty()) ans += stk.top() - i - 1;
        else ans += n - i;
        stk.push(i);
    }

    printf("%lld", ans);

    return 0;
}

三、单调队列

单调队列的定义类似于单调栈：

单调递增队列： 从队尾到队头单调递增；
单调递减队列： 从队尾到队头单调递减。

例如对于单调递增队列，向其中插入元素的时候，为了维护队列的单调性，需要在保证将该元素插入到队尾后整个队列满足单调性的前提下弹出最少的元素（从队尾弹出）：

deque<int> q;  // 因为涉及到从队尾弹出，所以只能用双端队列来实现单调队列

void insert(int x) {
    while (!q.empty() && q.back() < x)
        q.pop_back();
    q.push_back(x);
}

⚠️ 严格意义上讲单调队列并不是队列，因为它不满足FIFO。

四、单调队列的应用

4.1 滑动窗口

原题链接：AcWing 154. 滑动窗口

单调队列常用于求滑动窗口中的最大（小）值。我们先来看一下这道题的暴力解法是什么样的：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL INF = 3e9;

LL a[1000010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i <= n - k; i++) {
        LL mini = INF;
        for (int j = i; j < i + k; j++) mini = min(mini, a[j]);
        cout << mini << ' ';
    }

    cout << "\n";

    for (int i = 0; i <= n - k; i++) {
        LL maxi = -INF;
        for (int j = i; j < i + k; j++) maxi = max(maxi, a[j]);
        cout << maxi << ' ';
    }

    return 0;
}

显然时间复杂度为 $O (nk)$ ，基本会TLE。使用单调队列，我们可以将时间复杂度降低至 $O (n)$ 。

以求最小值为例，我们使用单调递减队列来保存滑动窗口中的元素，下标越大的元素越接近队尾，下标越小的元素越接近队头，于是求滑动窗口中的最小值相当于访问队头元素。

不妨设下标从 $1$ 开始，初始时 $i$ 指向 $1$ ，并且 $i$ 从 $1$ 遍历至 $n$ ，每次遍历都将 $a [i]$ 插入到队列中。可以发现，只要有 $i < k$ 就说明滑动窗口还未形成，此时无需输出最小值，当 $i\geq k$ 时才需要输出最小值。

那何时弹出队头元素呢？不妨让单调队列保存的是元素的下标而非元素本身，设当前窗口为 $a [i - k .. i - 1]$ ，向单调队列插入 $i$ 后，新窗口变成 $a [i - k + 1.. i]$ ，如果队头元素小于等于 $i - k$ ，说明最小值不在新窗口中，此时应当弹出队头元素。

到目前为止，可以总结出两点：

只要 $i\geq k$ 就应当输出队头元素；
当队头元素小于等于 $i - k$ 时，弹出队头元素。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int a[N];
deque<int> q;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if (!q.empty() && q.front() <= i - k) q.pop_front();  // 既可以用if也可以用while
        if (i >= k) cout << a[q.front()] << ' ';
    }

    cout << "\n";
    q.clear();

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] < a[i]) q.pop_back();
        q.push_back(i);
        if (!q.empty() && q.front() <= i - k) q.pop_front();  // 既可以用if也可以用while
        if (i >= k) cout << a[q.front()] << ' ';
    }

    return 0;
}

此题还可以用优先队列来做，为避免不必要的判断，我们可以在一开始就向队列中插入前 $k$ 个元素：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e6 + 10;

int a[N];
priority_queue<PII> p;  // 大根堆
priority_queue<PII, vector<PII>, greater<>> q;  // 小根堆

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= k; i++) q.emplace(a[i], i);
    cout << q.top().first << ' ';

    for (int i = k + 1; i <= n; i++) {
        q.emplace(a[i], i);
        while (!q.empty() && q.top().second <= i - k) q.pop();  // 只能用while
        cout << q.top().first << ' ';
    }

    cout << "\n";

    for (int i = 1; i <= k; i++) p.emplace(a[i], i);
    cout << p.top().first << ' ';

    for (int i = k + 1; i <= n; i++) {
        p.emplace(a[i], i);
        while (!p.empty() && p.top().second <= i - k) p.pop();  // 只能用while
        cout << p.top().first << ' ';
    }

    return 0;
}

观察上面两段代码，可以发现思路是大致相同的，但区别在于（请看注释行），单调队列在弹出队头元素的时候既可以用 if 也可以用 while，而优先队列弹出队头元素的时候只能用 while，这是为什么呢？

考虑数组 $[4, 6, 2, 3, 5, 1, 8, 7, 9]$ ，窗口大小为 $3$ ，以求最小值为例，每次循环结束后单调队列和优先队列的状态列在下表中：

⚠️ 列表的左端是队头，右端是队尾。
⚠️ 对于优先队列，只需看列表的第一个元素，其后元素的次序无关紧要。

滑动窗口	单调队列	优先队列
$[4, 6, 2]$	$[2]$	$[2, 4, 6]$
$[6, 2, 3]$	$[2, 3]$	$[2, 4, 6, 3]$
$[2, 3, 5]$	$[2, 3, 5]$	$[2, 4, 6, 3, 5]$
$[3, 5, 1]$	$[1]$	$[1, 2, 4, 6, 3, 5]$
$[5, 1, 8]$	$[1, 8]$	$[1, 2, 4, 6, 3, 5, 8]$
$[1, 8, 7]$	$[1, 7]$	$[1, 2, 4, 6, 3, 5, 8, 7]$
$[8, 7, 9]$	$[7, 9]$	$[7, 8, 9]$

因为优先队列在插入元素的过程中不会弹出元素，所以只要队头位于窗口内，那么优先队列的大小只增不减，这就导致优先队列中存在许多冗余元素（不属于窗口内的元素）。而单调队列为了保持单调性，插入元素的时候会从队尾弹出一些元素，这就保证了单调队列中的元素始终是滑动窗口中的元素的子集，因此单调队列的 while 循环至多执行一次，自然可以改成 if。

猜你喜欢

删除推文存档平台PostGhost宣布关闭
ubuntu下配置安装conky
小程序当中的文件类型，组织结构，配置，知识点等
UWA两周年福利帖 | 给你一个暑“价”，回归小清新的性能！
泰克的创新史，就是示波器的创新史
加减乘除工具类BigDecimalUtil
1048 数字加密 (20 分)C语言
一文彻底理解 Cookie、Session、Token
《有效的单元测试》一第1章优秀测试的承诺
GEE——巴西年度土地覆盖下载和地图展示（Mapbiomas 集成包）内含使用教程和下载链接
table与json的互转
2016就快结束了

相关主题

15.消息队列RabbitMQ
数据结构之栈与队列

zl程序教程