0239. 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:
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]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Example 5:
Input: nums = [4,-2], k = 2
Output: [4]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Analysis: using Deque¶
We need to maintain a queue, where the front stores the current max in the sliding window. When we want to push a new element to the queue, we first need to kick off all the elements that are not in the range (from i to i + k - 1), and then we need to keep pop_back() the element(s) that is/are less than current nums[i]. In order to achieve the pop_front() and push_back() operations, we need to use std::dequeue data structure in order to achieve these two operations running in O(1).
- Time: O(n) since each element can get in and get out of the deque only once
- Space: O(k) the maximum size of the deque is having all the window size elements (e.g. a decreasing array-like 5,4,3,2,1, so each element will be pushed into the deque).
Code 1: using Deque¶
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
if (dq.empty()) dq.push_back(i);
else {
// remove idx that is out of bound
while (!dq.empty() && dq.front() <= i - k)
dq.pop_front();
// remove the element in front of current that is less than current
while (!dq.empty() && (nums[dq.back()] < nums[i]))
dq.pop_back();
dq.push_back(i);
}
if (i >= k - 1) { // start pushing when the first window is of size k
res.push_back(nums[dq.front()]);
}
}
return res;
}
};
Analysis: using montonic Deque¶
After the observation of the deque data structure we are using, we find what it stores is a non-increasing array of elements (e.g. 3,2,2,1). We can then abstract the data structure into a class, so that we can just push(int) and pop() from the class.
- Time: same
- Space: same
Code 2: Montonic Deque¶
class MonoQueue {
public:
void push(int e) {
while (!data_.empty() && e > data_.back()) {
data_.pop_back();
}
data_.push_back(e);
}
void pop() {
data_.pop_front();
}
int max() const {
return data_.front();
}
private:
deque<int> data_;
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonoQueue q;
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
q.push(nums[i]); // we can push worry-free
if (i - k + 1 >= 0) {
ans.push_back(q.max());
if (nums[i - k + 1] == q.max()) // the front of the queue is the greatest element (duplicate is fine)
q.pop();
}
}
return ans;
}
};