Sliding Window Maximum
Problem Description
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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest way to solve the sliding window maximum problem is to compute the maximum of each window separately. For each position in the array, consider all the elements in the sliding window starting from that position, and find the maximum element. This method checks each sliding window one by one and finds the maximum element.
Code:
- Time Complexity: O(N * K): N is the number of elements in the array, and K is the size of the window. For each of the N-K+1 windows, finding the maximum requires O(K) time.
- Space Complexity: O(N-K+1): We only need an array to store the results.
2. Deque (Double-Ended Queue) Approach
Intuition:
Using a deque, we maintain the indexes of the array. The key is to maintain the elements of the deque in a monotonically decreasing order of their values. This means the max value for the window is at the front of the deque. We ensure that elements outside the current window or smaller elements than the current are removed.
Code:
- Time Complexity: O(N) - Each element is added and removed from the deque at most once.
- Space Complexity: O(K) - Deque holds at most K elements.
3. Max-Heap Approach
Intuition:
This approach uses a max heap to store the elements of the current window. The largest element in the window is always at the top of the heap. We remove elements from the heap that are out of the window's current range.
Code:
- Time Complexity: O(N log K) - For each of the N elements, we insert and/or delete from the heap which has a log K time complexity.
- Space Complexity: O(K) - Max heap can hold up to K elements.