算法1

使用双端队列 Deque

时间复杂度

参考文献

Java 代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = s.nextInt();
        Deque<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        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.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
        System.out.println(sb.toString());
        q.clear();
        sb.setLength(0);
        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.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
        System.out.print(sb.toString());
    }
}