按道理也是 O(n) 的时间复杂度,想说和 y 总的有何不一样吗?
ps. Java 使用标准 IO 会超时,必须使用 buffer 输出
import java.util.*;
import java.io.*;
class Main {
private static int N = 1000009;
private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] s1 = reader.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int k = Integer.parseInt(s1[1]);
int[] arr = new int[N];
String[] s2 = reader.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(s2[i]);
}
int[][] ans = getMaxValue(arr, n, k);
for (int i = 0; i < 2; i++) {
int[] res = ans[i];
for (int val : res) {
log.write(val + " ");
}
log.write("\n");
}
log.flush();
log.close();
reader.close();
}
private static int[][] getMaxValue(int[] arr, int n, int k) {
int len = n - k + 1;
int[][] ans = new int[2][len];
Deque<Integer> minStack = new ArrayDeque<>();
Deque<Integer> maxStack = new ArrayDeque<>();
for (int i = 0; i < k - 1; i++) {
insertValue(minStack, arr, 0, i, false);
insertValue(maxStack, arr, 0, i, true);
}
for (int i = 0; i < len; i++) {
insertValue(minStack, arr, i, i + k - 1, false);
insertValue(maxStack, arr, i, i + k - 1, true);
ans[0][i] = arr[minStack.peekFirst()];
ans[1][i] = arr[maxStack.peekFirst()];
}
return ans;
}
private static void insertValue(Deque<Integer> stack, int[] arr, int start, int end, boolean isMaxStack) {
while (!stack.isEmpty() && stack.peekFirst() < start) {
stack.pollFirst();
}
int val = arr[end];
while (!stack.isEmpty() && (isMaxStack ? (arr[stack.peekLast()] <= val) : (arr[stack.peekLast()] >= val))) {
stack.pollLast();
}
stack.addLast(end);
}
}