Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
String[] nums = br.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(nums[i]);
}
int[] res_min = new int[n - k + 1];
int[] res_max = new int[n - k + 1];
Deque<Integer> queue_min = new LinkedList<>();
Deque<Integer> queue_max = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!queue_max.isEmpty() && arr[queue_max.peekLast()] <= arr[i]) {
queue_max.pollLast();
}
while (!queue_min.isEmpty() && arr[queue_min.peekLast()]>= arr[i]) {
queue_min.pollLast();
}
queue_max.offerLast(i);
queue_min.offerLast(i);
}
res_max[0] = arr[queue_max.peekFirst()];
res_min[0] = arr[queue_min.peekFirst()];
for (int i = k; i < n; i++) {
while(!queue_max.isEmpty() && arr[queue_max.peekLast()] <= arr[i]) {
queue_max.pollLast();
}
queue_max.offerLast(i);
if(queue_max.peekFirst() <= i - k) {
queue_max.pollFirst();
}
res_max[i - k + 1] = arr[queue_max.peekFirst()];
}
for (int i = k; i < n; ++i) {
while (!queue_min.isEmpty() && arr[queue_min.peekLast()] >= arr[i]) {
queue_min.pollLast();
}
queue_min.offerLast(i);
if(queue_min.peekFirst() <= i - k) {
queue_min.pollFirst();
}
res_min[i - k + 1] = arr[queue_min.peekFirst()];
}
for (int num : res_min) {
System.out.print(num + " ");
}
System.out.println();
for (int num : res_max) {
System.out.print(num + " ");
}
}
}