与普通滑动窗口不同,该题
1 窗口大小固定,遍历左端点,可计算得右端点
2 双端队列作为单调栈存储到此为止的滑动窗口内的最值
3 模拟队列比Deque更好用
数组模拟代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++ ) {
a[i] = sc.nextInt();
}
int[] q = new int[n];
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ) {
if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
while ( hh <= tt && a[i] <= a[q[tt]]) tt -- ;
q[++ tt] = i;
if (i + 1 >= k) System.out.print(a[q[hh]] + " ");
}
System.out.println();
hh = 0;
tt = -1;
for (int i = 0; i < n; i ++ ) {
if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
while (hh <= tt && a[i] >= a[q[tt]]) tt -- ;
q[++ tt] = i;
if (i + 1 >= k) System.out.print(a[q[hh]] + " ");
}
}
}
Deque代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++ ) {
a[i] = sc.nextInt();
}
Deque<Integer> q = new LinkedList<>(); // 使用单调队列来保存当前滑动窗口内最大值的下标
for (int i = 0; i < n; i ++ ) {
if (!q.isEmpty() && i - q.peekFirst() + 1 > k) q.pollFirst();
while (!q.isEmpty() && a[i] <= a[q.peekLast()]) q.pollLast();
q.offerLast(i);
if (i + 1 >= k) System.out.print(a[q.peekFirst()] + " ");
}
q.clear();
System.out.println();
for (int i = 0; i < n; i ++ ) {
if (!q.isEmpty() && i - q.peekFirst() + 1 > k) q.pollFirst();
while (!q.isEmpty() && a[i] >= a[q.peekLast()]) q.pollLast();
q.offerLast(i);
if (i + 1 >= k) System.out.print(a[q.peekFirst()] + " ");
}
}
}