# [recommend for beginners]clean C++ implementation with detailed explanation

• Priority-queue based solution

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
/*** use the multiset to get the max-value ***/
multiset<int> w;
for(int i=0; i<nums.size(); i++){
/*** erase the previous top element ***/
if(i>=k)  w.erase(w.find(nums[i-k]));
w.insert(nums[i]);
/*** insert the max-value of the window ***/
if(i>=k-1) result.push_back(*w.rbegin());
}
return result;
}
};
``````

O(N) deque-monotical-queue-solution

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> q;
for(int i=0; i<nums.size(); i++){
/*** remove the top element **/
if(!q.empty() && q.front()==i-k)  q.pop_front();
/*** keep the element in the queue is monotically-decreasing ***/
while(!q.empty() && nums[q.back()] < nums[i])  q.pop_back();
q.push_back(i);
if(i>=k-1)  result.push_back(nums[q.front()]);
}
return result;
}
};``````

• I have to summary here:

The first solution just use the multiset(), which is a good choice for us.

The second solution is to use the Mono-Decreasing-Queue.

It keeps the biggest element lays at the front position!

• Once AC implementation

``````class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
multiset<int> window;
for(int i = 0; i < nums.size(); i ++) {
if(i >= k) {
window.erase(window.find(nums[i-k]));
}
window.insert(nums[i]);
if(i >= k-1) {
result.push_back(*window.rbegin());
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.