AcWing 154. 滑动窗口JAVA
原题链接
简单
作者:
理想二旬.
,
2021-05-07 19:02:03
,
所有人可见
,
阅读 344
JAVA 代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main{
private static int N = 1000010;
private static int[] a = new int[N];
private static int[] q = new int[N]; //滑动队列 存放的是下标
public static void main(String[] args) throws IOException{
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
int n = Integer.parseInt(str1[0]);
int k = Integer.parseInt(str1[1]);
String[] str2 = reader.readLine().split(" ");
for(int i = 0; i < n; i++){
a[i] = Integer.parseInt(str2[i]);
}
int hh = 0; // 队列头 头在左
int tt = -1; // 队列尾 尾在右
//输出滑动窗口里的最小值
for(int i = 0; i < n; i++){
//判断队列头是否已经滑出窗口,维护队列始终最多是k个元素
//hh <= tt --- 队列是否为空
// i - k + 1 > q[hh] --- 该滑出去了
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)
writer.write(a[q[hh]] + " ");
}
writer.write("\n");
//输出滑动窗口里的最大值
//初始化滑动队列
hh = 0; tt = -1;
for(int i = 0; i < n; i++){
//判断队列头是否已经滑出窗口,维护队列始终最多是k个元素
//hh <= tt --- 队列是否为空
// i - k + 1 > q[hh] --- 该滑出去了
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)
writer.write(a[q[hh]] + " ");
}
writer.flush();
reader.close();
writer.close();
}
}