Sliding Window Maximum — Monotonic Deque

# Python
from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices; front = max
    res = []
    for i, x in enumerate(nums):
        # Remove out-of-window from front
        while dq and dq[0] <= i - k: dq.popleft()
        # Remove smaller from back
        while dq and nums[dq[-1]] < x: dq.pop()
        dq.append(i)
        if i >= k - 1: res.append(nums[dq[0]])
    return res

// Java
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length; int[] res = new int[n-k+1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i-k) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k-1) res[i-k+1] = nums[dq.peekFirst()];
    }
    return res;
}

// C++
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; vector<int> res;
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!dq.empty() && dq.front() <= i-k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k-1) res.push_back(nums[dq.front()]);
    }
    return res;
}