Given n values and a window size k, print the maximum of every window of k consecutive values — in O(n) total, not O(n·k).
Write WindowMax using an ArrayDeque<Integer> of indexes whose values are kept in decreasing order: before adding index i, remove from the back every index whose value is ≤ a[i]; remove the front when it has left the window; the front is then the maximum. Count every deque operation (each add and each removal).
For the input
8 3
1 3 -1 -3 5 3 6 7
the program prints
Window maximums: 3 3 5 5 6 7
Deque operations: 15 (at most 2n = 16)
A nested loop would compare 18 values