附近最小
作者:
不知名的fE
,
2025-02-04 19:00:41
,
所有人可见
,
阅读 2
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
//N开到2 * n题目没有说明k的大小,直接默认到n的数量级
static final int N = 2000010, INF = 0x3f3f3f3f;
static int[] a = new int[N], res = new int[N];
static int n, len;
public static void main(String[] args) {
/*
模板求解的是窗口为k的最小值,也就是没有求出窗口为小于k的最小值
有两个端点
对于前面不足k的部分我们采用不进行条件判断的方式,也就是直接加入res数组
对于后面的部分我们采用扩大arr的遍历范围,遍历到n + len(1开始的)这样就可以枚举到n的所有情况
为方便遍历到n+len,我们将后面的部分都设置为INF,确保不会被选择
*/
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
len = sc.nextInt();
for (int i = n + 1; i <= n + len; i++) a[i] = INF;
monoQueue(a, 2 * len + 1, res);
// 输出后n个
for (int i = 1 + len; i <= n + len; i++) {
System.out.print(res[i] + " ");
}
}
//单调队列模板
static void monoQueue(int[] arr, int k, int[] res) {
LinkedList<Integer> q = new LinkedList<>();
for (int i = 1; i <= n + len; i++) {
if (!q.isEmpty() && i - q.getFirst() >= k) q.removeFirst();
while (!q.isEmpty() && arr[q.getLast()] >= arr[i]) q.removeLast();
q.addLast(i);
res[i] = arr[q.getFirst()];
}
}
}