0239.md

239. Sliding Window Maximum

Level:

Topic:

Similar Problem:

• 76. Minimum Window Substring

Question

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

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

Window position                Max
-------------------------     -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Intuition

By looking at the problem example, simply keep a monotonic decreasing deque and everytime the window size is at k, the max is the first element in deque. As we shift to the right, we have to poll off the leftmost in the window, we only poll off from the deque when the leftmost in the window is the one correspond to the max in deque.

Window position                Max       Deque        Array
-------------------------     -----     ---------    --------
[1  3  -1] -3  5  3  6  7       3       {3, -1}      [3]
 1 [3  -1  -3] 5  3  6  7       3       {3, -1}      [3,3]
 1  3 [-1  -3  5] 3  6  7       5       {5}          [3,3,5]
 1  3  -1 [-3  5  3] 6  7       5       {5, 3}       [3,3,5,5]
 1  3  -1  -3 [5  3  6] 7       6       {6}          [3,3,5,5,6]
 1  3  -1  -3  5 [3  6  7]      7       {7}          [3,3,5,5,6,7]

Code

Time: O(n)
Space: O(k)

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int [] ans = new int[n-k+1];

    Deque<Integer> dq = new ArrayDeque<>();
    int left = 0, right = 0;

    int i = 0;
    while (right < n) {
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[right])
            dq.pollLast();
        dq.addLast(right);
        right++;

        if (right - left == k) {
            ans[i++] = nums[dq.peekFirst()];
            if (left == dq.peekFirst())
                dq.pollFirst();
            left++;
        }
    }

    return ans;
}