Sliding Window Maximum

Hard

Python

from collections import deque
def max_sliding_window(nums,k):
    q=deque(); res=[]
    for i,n in enumerate(nums):
        while q and nums[q[-1]]<n: q.pop()
        q.append(i)
        if q[0]==i-k: q.popleft()
        if i>=k-1: res.append(nums[q[0]])
    return res

Java

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

Key Insight

Monotonic deque. Python deque vs Java ArrayDeque. q[-1] vs peekLast().

Python → Java Differences

Python deque vs Java ArrayDeque
q[-1] vs peekLast()
Monotonic deque identical

Python

from collections import deque
def max_sliding_window(nums,k):
    q=deque(); res=[]
    for i,n in enumerate(nums):
        while q and nums[q[-1]]<n: q.pop()
        q.append(i)
        if q[0]==i-k: q.popleft()
        if i>=k-1: res.append(nums[q[0]])
    return res

Java

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

Algorithm Steps

1. Monotonic decreasing deque
2. Remove out-of-window
3. Front is window max

← Previous All Sliding Window