题目描述
给定一个大小为n≤106的数组。
有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。
您只能在窗口中看到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个整数,代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
难度:简单
求关注~~~
思路
利用单调队列解决问题
题目要求求出滑动窗口范围内所有的最大最小值,而且滑动窗口中数的操作也符合队列的性质,右移一位,队头出,队尾加,这正好符合单调队列的所有性质,单调队列的头部会保存当前窗口中的最小或者最大值。
本题数据模拟
q1单调递增队列 q2单调递减队列
窗口位置 队列q1 队列q2 最小值(q1队头) 最大值(q2队头)
0 1 2 3 4 5 6 7 (下标)
[1 3 -1] -3 5 3 6 7 [2] [1, 2] a[2] = -1 a[1] = 3
1 [3 -1 -3] 5 3 6 7 [3] [1, 2, 3] a[3] = -3 a[1] = 3
1 3 [-1 -3 5] 3 6 7 [3, 4] [4] a[3] = -3 a[4] = 5
1 3 -1 [-3 5 3] 6 7 [3, 5] [4, 5] a[3] = -3 a[4] = 5
1 3 -1 -3 [5 3 6] 7 [5, 6] [6] a[5] = 3 a[6] = 6
1 3 -1 -3 5 [3 6 7] [5,6,7] [7] a[5] = 3 a[7] = 7
至此完成了所有过程的遍历
```
//单调递减
for(int i = 0; i < n; i ++){
//用于检测队列范围,当前元素位置i - k + 1(计算的实际队头位置) 大于队列中的队头,则队头元素出列
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
//比较元素
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
//加入当前元素
q[++ tt] = i;
// 如果当前元素位置i大于k - 1位置,则输出
if(i >= k - 1) bw.write(a[q[hh]] + " ");
}
//单调递增
for(int i = 0; i < n; i ++){
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[++ tt] = i;
if(i >= k - 1) bw.write(a[q[hh]] + " ");
}
```
java
import java.io.*;
public class Main{
static int n, k;
static int N = 1000010;
static int[] q = new int[N], a = new int[N];
static int hh = 0, tt = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
String[] s = br.readLine().split(" ");
for (int i = 0; i < n; i++)
a[i] = Integer.parseInt(s[i]);
for(int i = 0; i < n; i ++){
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[++ tt] = i;
if(i >= k - 1) bw.write(a[q[hh]] + " ");
}
bw.write("\n");
hh = 0; tt = -1;
for(int i = 0; i < n; i ++){
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if(i >= k - 1) bw.write(a[q[hh]] + " ");
}
bw.write("\n");
bw.flush();
br.close();
bw.close();
}
}
python3
N = 1000010
a = [0] * N
q = [0] * N
hh, tt = 0, -1
def main():
global a, q, tt, hh
n, k = list(map(int, input().split(" ")))
a = list(map(int, input().rstrip().split(" ")))
for i in range(n):
if(hh <= tt and i - k + 1 > q[hh]): hh +=1
while(hh <= tt and a[q[tt]] >= a[i]): tt -= 1
tt += 1
q[tt] = i
if(i >= k - 1): print(a[q[hh]], end=" ")
print()
i, hh, tt = 0, 0, -1
for i in range(n):
if(hh <= tt and i - k + 1 > q[hh]): hh +=1
while(hh <= tt and a[q[tt]] <= a[i]): tt -= 1
tt += 1
q[tt] = i
if(i >= k - 1): print(a[q[hh]], end=" ")
print()
main()
c++
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N], q[N];
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
int hh = 0, tt = -1;
for(int i = 0; i < n; i ++){
//先看队头是否已经滑出了窗口,这里可以不用while,每次只移出一格
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --; //如果队尾元素大于当前的元素a[i],出栈
q[++ tt] = i; //先加入,比如a:1, 3, -1, k : 3 经过上面的操作,队列里面保留为-1, 接下来在将-1输出
if(i >= k - 1) printf("%d ", a[q[hh]]); //取出队头,因为队列中保存的是顺序的单调递增序列,队头必然是最小的
}
puts("");
hh = 0, tt = -1;
for(int i = 0; i < n; i ++){
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
可以的
版主写的很棒,经常看版主的题解,但我想问下前面的单调递减和单调递增是不是笔误写反了呀,按逻辑来说 a[q[tt]] >= a[i]条件符合 不断弹出元素得到的应该是递增的呀 eg:[1,2,3,4,5]
改过来了,没有细看,谢谢指正!
这个太难了
但我想请教一下,为什么反过来输出——单调递增队列输出队尾求最小值,会出错?
单调递增队列,其队头是最小的值,队尾只是保存了后续可能存在的最小值索引(毕竟右移一个单位,会将队头元素移除)
写的很不错,很详细!