题目描述
一个长度为k的窗口在数组上进行滑动,求窗口内最值的问题
【初次接触时,理解难度大,需要深刻思考并且多次练习才能逐渐掌握一点】
解题思路
(1)为什么队列存储元素的下标?
①方便判断队头元素何时出队,数值的大小是变化的,而下标的滑动是按顺序的;
(2)为什么队列存储的窗口内是从最值到尾元素的一个单调性子序列?
①当前值≥队尾值时(求最大值时),队尾出队,即保证了此时窗口内含最大值;
②通过观察中间过程加深理解:
对于样例
8 3
1 3 -1 -3 5 3 6 7
分析其中推理过程,q[i](i)表示 数据(数组中对应的下标)
当i=0时 队列元素情况:1(0)
当i=1时 队列元素情况:3(1)
当i=2时 队列元素情况:3(1) -1(2)
当i=3时 队列元素情况:3(1) -1(2) -3(3)
当i=4时 队列元素情况:5(4)
当i=5时 队列元素情况:5(4) 3(5)
当i=6时 队列元素情况:6(6)
当i=7时 队列元素情况:7(7)
(3)窗口区间的表示
[i-k+1,i],此外q[hp]在区间内则认为队头在窗口中,不用出队;
(4)for循环体中的四行代码顺序一定不能颠倒。
①先判断窗口长度是否为k;
②队头是否为最值
③将下标存入队列;
④读取队头
算法1
时间复杂度 $O(n)$
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],q[N];
int main()
{
//input
int n,k;
scanf("%d%d",&n,&k);
//processing
for(int i = 0 ;i<n;i++) scanf("%d",&a[i]);
int hp = 0,tp = -1;
for(int i = 0;i < n;i++)
{
if(hp<=tp&&i-k+1>q[hp]) hp++;
while(hp<=tp&&a[q[tp]]>=a[i]) tp--;
q[++tp] = i;
if(i>=k-1) printf("%d ",a[q[hp]]);
}
puts("");
hp = 0,tp = -1;
for(int i = 0;i < n;i++)
{
if(hp<=tp && i-k+1>q[hp]) hp++; //q[hp]不在窗口[i-k+1,i]内,队头出队 ①窗口区间表示
while(hp<=tp && a[q[tp]]<=a[i]) tp--; //当前值≥队尾值时,队尾出队①队列为窗口的一个单调子序列
q[++tp] = i; //为什么队列存储元素的下标?①方便判断队头元素出队
//使用队头最大值
if(i>=k-1) printf("%d ",a[q[hp]]);
//a[i](i)表示 数据(数组中对应的下标)
//for(int j = hp;j<=tp;j++) cout<<a[q[j]]<<"("<<q[j]<<") ";
//cout<<endl;
}
puts("");
return 0;
}