Skip to main content

单调队列

Summary

单调队列是队内元素保持单调递增或递减的数据结构，支持从队头删除过期元素、从队尾弹出破坏单调性的元素，每个元素恰好入队出队各一次，总复杂度 O(n)。最典型的应用是滑动窗口最值：给定序列与窗口大小 k，求每个长为 k 的子区间的最值。维护单调递增队列，队头始终是当前窗口的最小值；新元素入队前从队尾弹出所有不小于它的元素，队头下标超出窗口则从队头弹出。给出求窗口最小值的实现。

参考资料​

简介​

单调队列（Monotonic Queue）是一种队列内元素保持单调递增或单调递减的数据结构，支持从队头删除过期元素、从队尾弹出不满足单调性的元素，每个元素恰好入队出队各一次，总时间复杂度 O(n)O(n)。

最典型的应用是求滑动窗口最值：给定长度为 nn 的序列和窗口大小 kk，求每个长度为 kk 的子区间的最小值（或最大值）。维护一个单调递增的队列，队头始终是当前窗口的最小值；新元素入队前从队尾弹出所有不小于它的元素以保持单调性；若队头下标超出窗口范围则从队头弹出。

实现​

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

const int N=1000005;
int a[N],q[N];
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];
	int hd=1,tl=0;
	for(int i=1;i<=n;i++)
	{
		while(hd<=tl&&a[q[tl]]>=a[i])tl--;
		q[++tl]=i;
		while(q[hd]<i-k+1)hd++;
		if(i>=k)cout<<a[q[hd]]<<' ';
	}
	return 0;
}

例题​

洛谷 P1886 【模板】单调队列 / 滑动窗口

有一个长为 nn 的序列 aa，以及一个大小为 kk 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。