什么是单调队列
单调队列是一种通过维护元素单调性(递增或递减)来优化算法效率的数据结构,常用于处理滑动窗口最大值/最小值、动态规划等问题。其核心特性包括:
核心特性
◉单调性:队列中的元素保持递增或递减排列,例如单调递增队列中元素从队头到队尾逐渐增大,单调递减队列则逐渐减小。
◉高效操作:通过维护单调性,每个元素最多进出队列一次,时间复杂度稳定为O(n)。
典型应用场景
◉滑动窗口问题:如求每个窗口内的最大值或最小值,通过维护单调递减队列实现高效查询。
◉动态规划优化:在背包问题等场景中,单调队列可将复杂问题转化为简单问题,提升算法效率。
实现要点
◉插入操作:从队尾插入元素,若新元素破坏单调性则移除尾部元素。
◉删除操作:根据需求从队首或队尾移除元素,保留有效信息。
模板题环节(题目链接:洛谷题目)(题目链接:ACGO题目)
题目介绍
有一个长为 n 的序列 a,以及一个大小为 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 个整数,表示序列 a。
输出格式
输出共两行,第一行为每次窗口滑动的最小值;
第二行为每次窗口滑动的最大值。
输入输出样例
输入#1
8 3
1 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明/提示
【数据范围】
对于 50% 的数据,1≤n≤10的5次方;
对于 100% 的数据,1≤k≤n≤10的6次方,a[i]∈[−2的31次方,2的31次方)
都看到这了点个赞呗❤
—可怜的作者