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


  • 6

    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;
        }
    };

  • 1

    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!


  • 0
    2

    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;
        }
    };

Log in to reply
 

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