Gamified challenge · Monotonic deque
temps[i] is the i-th temperature reading (it can be below zero). A window of k readings slides from the start of the log to the end, one reading at a time, with 1 ≤ k ≤ len(temps).
Write windowMax(temps, k) that returns a list with the highest reading in each window, in order: len(temps) - k + 1 numbers. For temps = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3 the answer is [3, 3, 5, 5, 6, 7].
Rescanning each window costs O(n·k). A deque of candidate indices, kept in falling order, gets every peak in O(n) overall.
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google