c++ multiset


  • 0
    T
    /*	Mine
    	用multiset作为sliding window
    	维护长度为k的window,出一个,进一个,然后取最大值
    */
    class Solution {
    
    private:
        multiset<int> window;
        void push(int x)
        {
            window.insert(x);
            return ;
        }
        void pop(int x)
        {
            multiset<int>::iterator it = window.find(x);
            window.erase(it);
            return ;
        }
        int getMax()
        {
            multiset<int>::reverse_iterator it = window.rbegin();
            return (*it);
        }
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ans;
            int len=nums.size();
            if (len==0) return ans;
            window.clear();
            for(int i=0;i<k;i++) push(nums[i]);
            ans.push_back(getMax());
            int kt=k-1,lent=len-1;
            for(int left=0,right=k;right<len;left++,right++)
            {
                pop(nums[left]);
                push(nums[right]);
                ans.push_back(getMax());
            }
            return ans;
        }
    };
    

Log in to reply
 

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