[单调队列]滑动窗口 /【模板】单调队列

作者：秋刀鱼在做梦 | 2024-08-17 17:45:54

踩

$滑动窗口 / 【模板】单调队列$

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

例如：
在这里插入图片描述

The array is [1,3,−1,−3,5,3,6,7] and k=3。

输入一共有两行，第一行有两个正整数 n,k。第二行 n 个整数，表示序列 a

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

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

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

对于 50% 的数据，1≤n≤10⁵；
对于 100% 的数据，1≤k≤n≤10⁶¹，ai∈[−2³¹,2³¹)。

#include<stdio.h>
#include<iostream>
using namespace std;
1
2
3

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/993823