The monotone deque

from collections import deque

def window_maximum(nums, k):
    dq = deque()                    # indices; their values fall from front to back
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:     # dominated: leaves sooner and is no larger
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                   # the front has left the window
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

#include <deque>
#include <vector>

std::vector<int> solve(const std::vector<int>& nums, int k) {
    std::deque<int> dq;                 // indices; values fall from front to back
    std::vector<int> out;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();     // the front has left the window
        if (i >= k - 1) out.push_back(nums[dq.front()]);
    }
    return out;
}

class Solution {
    public int[] windowMaximum(int[] nums, int k) {
        int n = nums.length;
        int[] dq = new int[n];          // indices in dq[head..tail); values fall front to back
        int head = 0, tail = 0;
        int[] out = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            while (tail > head && nums[dq[tail - 1]] <= nums[i]) tail--;
            dq[tail++] = i;
            if (dq[head] <= i - k) head++;              // the front has left the window
            if (i >= k - 1) out[i - k + 1] = nums[dq[head]];
        }
        return out;
    }
}

function windowMaximum(nums, k) {
  const dq = new Array(nums.length);   // a deque of indices in a plain array: dq[head..tail)
  let head = 0, tail = 0;
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    while (tail > head && nums[dq[tail - 1]] <= nums[i]) tail--;   // dominated candidates leave
    dq[tail++] = i;
    if (dq[head] <= i - k) head++;                               // the front has left the window
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}

use std::collections::VecDeque;

fn solve(nums: &[i64], k: i64) -> Vec<i64> {
    let k = k as usize;
    let mut dq: VecDeque<usize> = VecDeque::new();   // indices; values fall front to back
    let mut out = Vec::new();
    for i in 0..nums.len() {
        while let Some(&j) = dq.back() {
            if nums[j] > nums[i] {
                break;
            }
            dq.pop_back();
        }
        dq.push_back(i);
        if dq[0] + k <= i {
            dq.pop_front();                          // the front has left the window
        }
        if i + 1 >= k {
            out.push(nums[dq[0]]);
        }
    }
    out
}

import Data.Array
import qualified Data.Sequence as Seq
import Data.Sequence (ViewL(..), ViewR(..), viewl, viewr, (|>))

solve :: [Int] -> Int -> [Int]
solve xs k = go 0 Seq.empty
  where
    n = length xs
    arr = listArray (0, n - 1) xs
    -- the deque holds indices; their values fall from front to back
    go i dq
      | i == n = []
      | otherwise =
          let dropBack d = case viewr d of
                rest :> j | arr ! j <= arr ! i -> dropBack rest
                _ -> d
              pushed = dropBack dq |> i
              live = case viewl pushed of
                j :< rest | j <= i - k -> rest          -- the front has left the window
                _ -> pushed
              front = case viewl live of
                j :< _ -> arr ! j
                EmptyL -> 0
          in if i >= k - 1 then front : go (i + 1) live else go (i + 1) live