C++_AC_two methods(map+priority vs deque)


  • 0
      1. Using unordered_map + priority_queue, but it is very slow, only beats less than 10% submissions.
    class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return nums;
        unordered_map<int,int> mp;
        priority_queue<int> PQ;
        int i = 0, cnt = 0, n = nums.size();
        vector<int> res;
        while(i < n){
            if(cnt < k){
                while(cnt < k){
                    mp[nums[i]]++;
                    PQ.push(nums[i]);
                    i++;
                    cnt++;
                }
            }else{
                int tmp = nums[i - cnt];
                if(--mp[tmp] == 0) mp.erase(tmp);
                PQ.push(nums[i]);
                mp[nums[i]]++;
                while(mp.find(PQ.top()) == mp.end()){
                    PQ.pop();
                }
                ++i;
            }
            res.push_back(PQ.top());
        }
        return res;
    }
    };
    

      1. Using deque. Much faster, O(n) time & space.
        Each time when we push certain element into our deque, we remove all the elements which is less than our current value.
    class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return nums;
        vector<int> res;
        deque<pair<int,int>> DQ;//value - index 
        //Each time when we push certain element into our deque, we remove all the elements which is less than our current value, because, from now on, the max value could not be less than our current value.
        int i = 0, n = nums.size();
        while(i < n){
            while(!DQ.empty() && DQ.front().first <= nums[i]) DQ.pop_front();
            while(!DQ.empty() && DQ.back().first <= nums[i]) DQ.pop_back();
            DQ.push_back({nums[i],i});
            if(i - DQ.front().second + 1 > k) DQ.pop_front();
            if(i >= k - 1){
                res.push_back(DQ.front().first);
            }
            i++;
        }
        return res;
    }
    };

Log in to reply
 

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