Sliding Window Maximum [Hard] — Monotonic Decreasing Deque

Problem Statement

Given array nums and integer k, return an array of maximums for each sliding window of size k.

Input: nums=[1,3,-1,-3,5,3,6,7], k=3
Output: [3,3,5,5,6,7]

Intuition

Monotonic deque (indices) in decreasing order of values. At each step:

Remove indices outside window (front of deque)
Remove indices with smaller values than current (back of deque)
Add current index
Front of deque is always the current window max

Solutions

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; vector<int> res;
    for(int i=0;i<nums.size();i++){
        while(!dq.empty()&&dq.front()<i-k+1) 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;
}

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+1) dq.pollFirst();
        while(!dq.isEmpty()&&nums[dq.peekLast()]<nums[i]) dq.pollLast();
        dq.addLast(i);
        if(i>=k-1) res[i-k+1]=nums[dq.peekFirst()];
    }
    return res;
}

Python

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()
    res = []
    for i, val in enumerate(nums):
        while dq and dq[0] < i-k+1: dq.popleft()
        while dq and nums[dq[-1]] < val: dq.pop()
        dq.append(i)
        if i >= k-1: res.append(nums[dq[0]])
    return res

Complexity

Time: O(n) — each element pushed/popped once
Space: O(k)