单调队列¶
单调队列的作用¶
单调队列是一种数据结构，它可以维护一个序列中的最大值或最小值。单调队列的特点是队列中的元素从头到尾单调递增或递减。
单调队列的常见应用是求解滑动窗口的最大值或最小值问题。具体的操作步骤如下：
-
遍历序列，每次将一个元素入队。
-
如果新入队的元素比队尾元素大（或小），则将队尾元素出队，直到队列满足单调性。
-
如果队首元素已经不在滑动窗口内，则将队首元素出队。
-
每次形成一个滑动窗口时，记录队首元素作为最大值或最小值。
例题 #1 滑动窗口 /【模板】单调队列¶
题目描述
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：
\(\begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}\)
输入格式
输入一共有两行，第一行有两个正整数 \(n,k\)。 第二行 \(n\) 个整数，表示序列 \(a\)
输出格式
输出共两行，第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值
【数据范围】 对于 \(50\%\) 的数据，\(1 \le n \le 10^5\)； 对于 \(100\%\) 的数据，\(1\le k \le n \le 10^6\)，\(a_i \in [-2^{31},2^{31})\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,a[N],q[N],h=1,r;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)//求窗口最小值
{
while(h<=r&&a[q[r]]>=a[i])r--;
q[++r]=i;
while(h<=r&&q[h]+m<=i)h++;
if(i>=m)printf("%d ",a[q[h]]);
}
printf("\n");
h=1,r=0;//求窗口最大值
for(int i=1;i<=n;i++)
{
while(h<=r&&a[q[r]]<=a[i])r--;
q[++r]=i;
while(h<=r&&q[h]+m<=i)h++;
if(i>=m)printf("%d ",a[q[h]]);
}
return 0;
}
例题 #2 环形最大子序和¶
题目描述
给定一个环，A[1],A[2],A[3],...A[n],其中A[1]的左边是A[n]. 求一个最大的连续和，长度不超过K。
输入格式
第一行两个整数N和K(1<=N<=100000 , 1<=K<=N) 接下来一行，n个整数[-1000,1000]
输出格式
满足条件的最大连续和以及起始位置和终止位置。 如果有多个结果，输出起始位置最小的，如果还是有多组结果，输出长度最短的。
100%的数据，n≤100000
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
int sum;
list<int> q;
int qz[N];
int n,K;
inline int mod(int x){
if(x>n)return x-n;
return x;
}
void solve(){
n=rd,K=rd;
for(int i=1;i<=n;i++){
a[i]=a[i+n]=rd;
}
int ans=a[1];
int ansl=1,ansr=1;
int l=1;
int sum=0;
for(int i=1;i<=2*n;i++){
qz[i]=qz[i-1]+a[i];
}
for(int i=1;i<=2*n;i++){
while(q.size()&&q.front()<i-K)q.pop_front();
if(q.size()){
if(qz[i]-qz[q.front()]>ans){
ans=qz[i]-qz[q.front()];
ansl=q.front()+1;
ansr=i;
}else if(qz[i]-qz[q.front()]==ans&&i-q.front()<ansr-ansl){
ans=qz[i]-qz[q.front()];
ansl=q.front()+1;
ansr=i;
}
}
while(q.size()&&qz[q.back()]>qz[i])q.pop_back();
q.push_back(i);
}
cout<<ans<<' '<<mod(ansl)<<' '<<mod(ansr)<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}