Back to DSA

Sliding Window Maximum

hard
Acceptance: 42%
ArraysSliding Window

An integer array and a window size k are given. A window of exactly k consecutive elements slides across the array one position at a time, from left to right. For each window position, report the maximum value within that window. Return all these maximum values as an array.

Examples

Example 1:
Input:nums = [4,2,5,1,3,7,2], k = 3
Output:[5,5,5,7,7]
Explanation: Windows: [4,2,5]->5, [2,5,1]->5, [5,1,3]->5, [1,3,7]->7, [3,7,2]->7.
Example 2:
Input:nums = [9], k = 1
Output:[9]
Explanation: A window of size 1 always contains just the element itself.

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyMerge Sorted ArrayeasyMove Zeroeseasy
00:00
import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.offerLast(i);
            if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }
}
Time complexityO(n)
Space complexityO(k)