Author:
Monotonic Decreasing Queue⚓︎
Keywords: Slide Window, Array
Situation⚓︎
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⚓︎
Example
- 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 |
- Input:
nums
= [1],k
= 1 - Output: [1]
Pseudo-code⚓︎
Pseudo-code
Pseudo-code
//--------------------------------------------
// Author = "Tianle Yuan"
//--------------------------------------------
class Monoqueue {
deque<int> myque; // The monotonic queue is constructed based on dequeue. Every element in this queue is maintained to be monotonously decreasing.
public:
//Monotonize: when push in a new element, keep popping out current back elements until E_back >= E_pushin.
void push(int n) {
while(!myque.empty() && myque.back() < n) myque.pop_back();
myque.push_back(n);
}
//"Large Front": return front element (magnitude compared after monotonization) in the data structure
int front() {
return myque.front();
}
//Pop "Large Front": if the value has already been popped previously (small than the current, we do not have to pop it again)
void pop(int n) {
if(n == myque.front())
myque.pop_front();
}
};
Explainations⚓︎
Monotonize & "Large Front"?
Assume our monotonic queue
looks like the below, and we need to monotonize it when pushing back elements in. Run the codes below:
myque
: [6, 2]myque.push(-3)
→-3
is smaller than any elements inside, which should stay in the queue back.-
myque.push(5)
- →
5
is bigger than-3
; pop out-3
, which is out. - →
5
is bigger than2
; pop out2
, which is out. - →
5
is smaller than6
; stop popping and push back 5.
- →
-
myque.front()
: 6 now is the "Large Front".
Answer⚓︎
Realization
solution.c++
class Monoqueue {
deque<int> myque;
public:
void push(int n) {
while(!myque.empty() && myque.back() < n) myque.pop_back();
myque.push_back(n);
}
int front() {
return myque.front();
}
void pop(int n) {
if(n == myque.front()) myque.pop_front();
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
Monoqueue mq;
vector<int> res;
for(int i = 0; i < nums.size(); ++i) { //scan all the elements
if(i < k-1) mq.push(nums[i]); //initialize the dequeue
else {
mq.push(nums[i]); //push in new element, monotonize queue
res.push_back(mq.front()); //record the "large front"
mq.pop(nums[i-k+1]); //start from the k-1 element, we pop the front of the monotonic queue
}
}
return res;
}
};
References:⚓︎
Last update:
January 15, 2023 07:02:57
Created: January 15, 2023 07:02:57
Created: January 15, 2023 07:02:57