AcWing 154. 滑动窗口JAVA模板(数据太大会超时)
原题链接
简单
作者:
巴韭特
,
2021-05-21 14:17:24
,
所有人可见
,
阅读 309
数组模拟单调队列
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] nums = new int[n];
int[] queue = new int[n]; //存放对应数字在nums中的下标,方便查找
for (int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
// 输出每个位置滑动窗口中的最小值
int prev = 0; // 队头指针
int tail = -1; // 队尾指针
for (int i = 0; i < n; i++) {
// 判断对头是否以及滑出滑动窗口
if (prev <= tail && i - k + 1 > queue[prev]) {
prev++;
}
// 若队尾数字大于等于当前数字nums[i],则永远不会被用到,将其从队尾移出,tail--
while (prev <= tail && nums[queue[tail]] >= nums[i]) {
tail--;
}
//将当前数字的下标加入到单调队列中
queue[++tail] = i;
if (i >= k - 1) {
System.out.print(nums[queue[prev]] + " ");
}
}
System.out.println();
// 输出每个位置滑动窗口中的最大值
prev = 0;
tail = -1;
for (int i = 0; i < n; i++) {
if (prev <= tail && i - k + 1 > queue[prev]) {
prev++;
}
//将上方代码的此部分改成 <= 即可
while (prev <= tail && nums[queue[tail]] <= nums[i]) {
tail--;
}
queue[++tail] = i;
if (i >= k -1) {
System.out.print(nums[queue[prev]] + " ");
}
}
}
}
直接使用LinkedList作为单调队列
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] nums = new int[n];
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
// 输出每个位置滑动窗口中的最小值
for (int i = 0; i < n; i++) {
// 判断对头是否以及滑出滑动窗口
if (!queue.isEmpty() && i - k + 1 > queue.peekFirst()) {
queue.removeFirst();
}
// 若队尾数字大于等于当前数字nums[i],则永远不会被用到,将其从队尾移出,tail--
while (!queue.isEmpty() && nums[queue.peekLast()] >= nums[i]) {
queue.removeLast();
}
//将当前数字的下标加入到单调队列中
queue.addLast(i);
if (i >= k - 1) {
System.out.print(nums[queue.peekFirst()] + " ");
}
}
System.out.println();
// 输出每个位置滑动窗口中的最大值
queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 判断对头是否以及滑出滑动窗口
if (!queue.isEmpty() && i - k + 1 > queue.peekFirst()) {
queue.removeFirst();
}
// 若队尾数字大于等于当前数字nums[i],则永远不会被用到,将其从队尾移出,tail--
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.removeLast();
}
//将当前数字的下标加入到单调队列中
queue.addLast(i);
if (i >= k - 1) {
System.out.print(nums[queue.peekFirst()] + " ");
}
}
}
}