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.
Examples:
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]Solution in Python
Approach:
- Use a Deque (Double-Ended Queue):
- We maintain a deque that stores indices of the elements in the current window. This allows us to efficiently keep track of the maximum element.
- The deque ensures that the element at the front is always the maximum of the current window.
- Sliding the Window:
- As the window slides, we add new elements and remove elements that are out of the window’s range.
- The deque stores the indices in decreasing order of their corresponding values in
nums.
- Efficiency:
- Each element is added and removed from the deque at most once, so the time complexity is O(n), which is optimal for this problem.
Python
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# Step 1: Initialize an empty deque and a result list
deq = deque()
result = []
# Step 2: Iterate over each element in the array
for i in range(len(nums)):
# Step 3: Remove elements that are out of the current window
# The window is represented by the indices [i-k+1, i]
if deq and deq[0] < i - k + 1:
deq.popleft() # Remove the left-most (oldest) element
# Step 4: Maintain a decreasing deque
# Remove elements from the back if they are smaller than the current element
while deq and nums[deq[-1]] < nums[i]:
deq.pop() # Remove elements that are not useful anymore
# Step 5: Add the current element's index to the deque
deq.append(i)
# Step 6: Once we have processed at least 'k' elements,
# the element at the front of the deque is the largest element for the current window
if i >= k - 1:
result.append(nums[deq[0]]) # Append the max element for the current window to the result list
# Step 7: Return the result list containing the max of each sliding window
return resultExplanation:
- Deque Initialization:
deq = deque()is initialized to store the indices of elements in the current window. It will maintain the indices of elements in decreasing order based on their values.result = []will store the maximum values for each window.
- Iterating Over the Array:
- For each element in the array (with index
i):- First, we check if there are any elements in the deque that are out of the bounds of the current window (
i-k+1is the starting index of the window). If so, we remove them from the front of the deque. - Next, we remove elements from the back of the deque while their value is smaller than the current element (
nums[i]), since they can’t be the maximum for the current or any future window. - Then, we append the current element’s index to the deque.
- First, we check if there are any elements in the deque that are out of the bounds of the current window (
- For each element in the array (with index
- Adding the Maximum to the Result:
- After processing the first
kelements, for each new window, the element at the front of the deque (deq[0]) is the index of the maximum element for that window. We addnums[deq[0]]to the result list.
- After processing the first
- Return the Result:
- Finally, after processing all elements, the
resultlist contains the maximums of all the sliding windows.
- Finally, after processing all elements, the
Solution in C++
C++
#include <vector>
#include <deque>
using namespace std;
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// Step 1: Initialize a deque to store indices and a result vector to store the output
deque<int> deq;
vector<int> result;
// Step 2: Traverse through the nums array
for (int i = 0; i < nums.size(); ++i) {
// Step 3: Remove elements from the front of the deque if they are out of the current window
if (!deq.empty() && deq.front() < i - k + 1) {
deq.pop_front(); // Remove the left-most element which is outside the window
}
// Step 4: Maintain the decreasing order in the deque
// Remove elements from the back of the deque if they are smaller than the current element
while (!deq.empty() && nums[deq.back()] < nums[i]) {
deq.pop_back(); // Remove elements that are smaller and not useful anymore
}
// Step 5: Add the current element index to the deque
deq.push_back(i);
// Step 6: Append the maximum of the current window (at the front of the deque) to the result
if (i >= k - 1) {
result.push_back(nums[deq.front()]); // The element at the front of deque is the largest for the current window
}
}
// Step 7: Return the result vector containing the maximum of each sliding window
return result;
}
};Solution in Javascript
JavaScript
var maxSlidingWindow = function(nums, k) {
// Step 1: Initialize the deque and the result array
let deq = [];
let result = [];
// Step 2: Iterate through the nums array
for (let i = 0; i < nums.length; i++) {
// Step 3: Remove elements from the front of the deque if they are out of the window's range
if (deq.length > 0 && deq[0] < i - k + 1) {
deq.shift(); // Remove the left-most element which is out of the window
}
// Step 4: Maintain the decreasing order in the deque
// Remove elements from the back of the deque that are smaller than the current element nums[i]
while (deq.length > 0 && nums[deq[deq.length - 1]] < nums[i]) {
deq.pop(); // Remove elements that are smaller than the current element
}
// Step 5: Add the current element's index to the deque
deq.push(i);
// Step 6: Once the first k elements are processed, append the max of the current window to the result
if (i >= k - 1) {
result.push(nums[deq[0]]); // The element at the front of the deque is the largest for the current window
}
}
// Step 7: Return the result array containing the max values of each sliding window
return result;
};Solution in Java
Java
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// Step 1: Initialize the deque to store indices and the result array
Deque<Integer> deq = new LinkedList<>();
int[] result = new int[nums.length - k + 1]; // Result array to store the maximums
int resIndex = 0; // Index to track position in the result array
// Step 2: Iterate through the nums array
for (int i = 0; i < nums.length; i++) {
// Step 3: Remove indices of elements that are out of the current window
if (!deq.isEmpty() && deq.peek() < i - k + 1) {
deq.poll(); // Remove the front element if it's outside the window
}
// Step 4: Maintain decreasing order in the deque
// Remove elements from the back of the deque that are smaller than the current element nums[i]
while (!deq.isEmpty() && nums[deq.peekLast()] < nums[i]) {
deq.pollLast(); // Remove elements that are smaller than nums[i]
}
// Step 5: Add the current element's index to the deque
deq.offer(i);
// Step 6: Start adding the maximum of the current window to the result array
if (i >= k - 1) {
result[resIndex++] = nums[deq.peek()]; // The front of the deque is the max for the current window
}
}
// Step 7: Return the result array containing the maximum values of each sliding window
return result;
}
}