239. Sliding Window Maximum
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:
Example 2:
Constraints:
- 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
- − 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
- 1 <= k <= nums.length
From: LeetCode
Link: 239. Sliding Window Maximum
Solution:
Ideas:
1. Initialization: The function starts by handling edge cases (e.g., empty input array) and then initializes variables for the result array, which will store the maximum values for each window, and the deque, which will store indices of elements in the array (not the elements themselves).
2. Deque as a Max Queue: The deque is used to keep track of potential candidates for the maximum value in the current window. It’s maintained in such a way that the indices of the largest elements are at the front, and it only contains indices of elements within the current window. This is achieved through two main operations as the window slides:
- Removing old indices: As the window moves forward, indices that are no longer within the window are removed from the front of the deque.
- Maintaining order: Before adding a new element’s index to the deque, indices of all elements smaller than the new element are removed from the back of the deque. This ensures that the deque always represents elements in decreasing order within the current window.
3. Adding New Indices and Updating Results: For each element in the array, the algorithm checks if any indices at the front of the deque are outside the current window and removes them. Then, it removes indices from the back of the deque if those elements are smaller than the current element. After updating the deque, if the window is at least of size k, the element corresponding to the front index in the deque (which is the maximum in the current window) is added to the result array.
4. Result Compilation: This process repeats for each element in the input array, effectively sliding the window across the entire array. For each position of the window, the maximum value is quickly identified (as the element corresponding to the front index in the deque) and stored in the result array.
5. Efficiency: The key to the algorithm’s efficiency lies in the deque’s maintenance, which ensures that both insertion and removal operations are O(1), and that each element is inserted and removed at most once. This guarantees an overall time complexity of O(n).
Code:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
if (numsSize == 0 || k == 0) {
*returnSize = 0;
return NULL;
}
*returnSize = numsSize - k + 1;
int* result = (int*)malloc(*returnSize * sizeof(int));
int* deque = (int*)malloc(numsSize * sizeof(int)); // Store indices
int front = 0, rear = -1;
for (int i = 0; i < numsSize; ++i) {
// Remove indices that are out of the current window
while (front <= rear && deque[front] < i - k + 1) {
front++;
}
// Remove from rear if the current element is greater than the deque's elements
while (front <= rear && nums[i] >= nums[deque[rear]]) {
rear--;
}
// Add the current element's index to the deque
deque[++rear] = i;
// If the window has reached its size k, add the maximum to the result array
if (i >= k - 1) {
result[i - k + 1] = nums[deque[front]];
}
}
free(deque);
return result;
}