LeetCode 239. Sliding Window Maximum

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.

Return the max sliding window.

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

Source: https://leetcode.com/problems/sliding-window-maximum/

Solution

As the window slides, we add a new element on right and discard an element on left. Because we discard elements from the window, we use a data structure to maintain all potential max values in the future (like LeetCode 155. Min Stack). Thus, we always push the new elment in to the queue when the window expands on right.

If we find that the new element is greater than several previous elements, it means that the new element becomes the new “guardian”. The previous guardians that are smaller than this new guardian can be removed from the queue. Because they will be discarded eariler than the new guardian and will never become the max. In other words, elements with a larger index and a larger corresponding value have an overwhelming advantage in competing for max.

The indexes in the monotonic queue are not necessarily consecutive. And this monotonic queue guarantees that these indexes are in ascending order and their corresponding elements in nums are in descending order.

Because we need to repeatedly remove elements from the head and tail of the queue and append elements to the tail of the queue, we choose LinkedList as the instance class of our monotonic queue.

// monotonic deque O(n)
public int[] maxSlidingWindow2(int[] nums, int k) {
    int len = nums.length;
    int[] result = new int[len - k + 1];
    // part indexes of elements in current window
    // i_{k}(max), i_{m}, i_{n}, ..., i_{right}
    // \head i_{k} < i_{m} < i_{n} < ... < i_{right} \tail
    // \head nums[i_{k}] >= nums[i_{m}] >= nums[i_{n}] >= ... >= nums[i_{right}] \tail
    Deque<Integer> monoDeque = new LinkedList<>();
    // queue initialization with the first window
    for (int i = 0; i < k; i++) {
        while (!monoDeque.isEmpty() && nums[monoDeque.getLast()] < nums[i]) {
            monoDeque.removeLast();
        }
        monoDeque.addLast(i);
    }

    result[0] = nums[monoDeque.getFirst()];
    int left = 1, right = k;
    for (; right < len; left++, right++) {
        // max is to be removed
        if (!monoDeque.isEmpty() && monoDeque.getFirst() == left - 1) {
            monoDeque.removeFirst();
        }
        while (!monoDeque.isEmpty() && nums[monoDeque.getLast()] < nums[right]) {
            monoDeque.removeLast();
        }
        monoDeque.addLast(right);
        result[left] = nums[monoDeque.getFirst()];
    }
    return result;
}