239. Sliding Window Maximum

Description of the Problem

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 <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Solution

Tags: Sliding Window Deque

The idea of solution is not largely come from myself. However, I would provide my explanation to show the correctness of the method.

Explanation

Use Deque with some constrains

Without loss of generality, assume the Deque stores tuples (i, x) where i is the index of x in array nums

Loop Invariant of the Deque \(d\): In j-th iteration, if the Deque \(d\) is not empty, then the following must be true

1. \( j \le d.head \land d.tail \lt j + k \ \) where \(k\) is the size of window
2. For any pair of tuples \((i, x)\), \((j, y)\) in the Deque \(d\): If \((i, x)\) is stored before \((j, y)\), then \(x\) must greater than \(y\). In other word, the Deque stores elements in descending order.

(1) is to ensure the values in the Deque are in the current window.

(2) is to ensure that the head of the Deque is always the largest element.

To make (1) true, remove 1 element from the head when moving window to the right

To make (2) true, before inserting the right-most element, remove all smaller elements from the tail.

Code (Java)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int [] ans = new int[ n - k + 1 ];
        Deque<Integer> q = new LinkedList<>();
        for(int j = 0; j < k; j++){
            while(q.size() != 0 && nums[q.peekLast()] < nums[j]){
                q.pollLast();
            }
            q.offerLast(j);
        }
        ans[0] = nums[q.peekFirst()];

        for(int i = 1; i <= n - k; i++){
            while(q.size() != 0 && q.peekFirst() < i){
                q.pollFirst();
            }

            while(q.size() != 0 && nums[q.peekLast()] < nums[i + k - 1]){
                q.pollLast();
            }
            q.offerLast(i + k - 1);
            ans[i] = nums[q.peekFirst()];
        }

        return ans;
    }
}