滑动窗口
题目题目分析算法分析源代码代码说明
题目
给定一个大小为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
题目分析
所要求的的是数组中的滑动窗口的最大值/最小值,朴素算法是维护一个数组队列,每次窗口移动从表头移除一个数,表位加入一个数,然后再在这个队列中遍历寻找最大值.问题在于每次求最大值都是对一个数组进行排序,那么能否简化这个操作,让求最大值的过程变得简单呢?
算法分析
答案就是选择单调队列.单调队列的核心就是去除掉队列中的无用元素,保持队列永远是有序的,这样项要求最大值/最小值只需要输出表头即可. 什么叫无用元素呢? 我们以求窗口的最小值为例.如果有一个新元素a[i]加入,那么在队列顶的元素如果大于a[i],那么这个原栈顶的存在就没有意义了,因为我们是以a[i]为队列尾,窗口是一定包扩队尾和队尾前的,只要有a[i]在,前边那个比a[i]大的数就一定会在选最小值中被a[i]遮蔽,因此之前的栈顶出栈,然后同样的操作多次进行.由于队列是按此规律搭建而成,因此任何时刻队列都是单调的. 当然,有一个需要注意的点,就是窗口的大小,因为窗口是有长度的,而队列是我们进行删减操作过的,因此,我们要找到删减后的队列里删减前的序号. 为什么呢? 因为如果窗口是3,插入的是a11的话,那我们要看的就是a9的位置为栈尾(如图,没有a9那就定位a10为栈尾,也就是此时栈内只要a10,a11),然后取出栈顶元素即可.
源代码
import java
.io
.*
;
class Main{
public static void main(String
[] args
)throws Exception
{
InputStreamReader is
=new InputStreamReader(System
.in
);
BufferedReader br
=new BufferedReader(is
);
BufferedWriter bw
=new BufferedWriter(new OutputStreamWriter(System
.out
));
String
[] s1
=br
.readLine().split(" ");
int n
=Integer
.parseInt(s1
[0]);
int k
=Integer
.parseInt(s1
[1]);
int N
=1000010;
int[] a
=new int[N
];
int[] q
=new int[N
];
String
[] s2
=br
.readLine().split(" ");
for(int i
=0;i
<n
;i
++){
a
[i
]=Integer
.parseInt(s2
[i
]);
}
int hh
=0,tt
=-1;
for(int i
=0;i
<n
;i
++){
if(hh
<=tt
&&q
[hh
]<i
-k
+1) 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
&&q
[hh
]<i
-k
+1) hh
++;
while(hh
<=tt
&&a
[i
]>=a
[q
[tt
]]){
tt
--;
}
q
[++tt
]=i
;
if(i
>=k
-1) bw
.write(a
[q
[hh
]]+" ");
}
bw
.flush();
br
.close();
bw
.close();
}
}
代码说明
最大值和最小值其实是很相近的,只不过队列的组成规则(即删减元素的规则变了),但是定位栈尾的要求依旧是不变的.超时问题: 通过这个题目可以看出,使用Scanner来进行输入,使用S.o.p来进行输出是很耗时的(虽然真的很好写). 想要更快的输入输出,应该选用io包中的bufferedReader,这里应该养成良好的习惯,直接默写:
BufferedReader br
=new BufferedReader(new InputStreamReader(System
.in
));
BufferedWirter bw
=new BufferWriter(new OutputStreamWriter(System
.out
));
String
[] s
=br
.readLine().split(" ");
int a
=Integer
.parseInt(s
[0]);
s
[1]=...
