Use a monotonic decreasing deque. Store indices, not values. The front always holds the index of the current maximum. When processing index : First, remove indices from the front that are outside the window (index ).
Second, remove indices from the back while . Third, add to the back. Why remove smaller elements? Because is both larger AND enters later. Those smaller elements will never be the maximum while is in the window.