【代码随想录算法训练Day13】LeetCode 239. 滑动窗口最大值、LeetCode 347.前K个高频元素

Day13 队列

LeetCode 239.滑动窗口最大值【队列】

本题我们的思想是维护一个新的队列，在加入新元素时把所有在他前面比他更小的元素全部删除，保证队首是滑动窗口内的最大值，只有在滑动窗口滑出时才会将队首的最大值删除，如果加入的是更小的数，那么就暂时加入进来。

class Solution {
private:
    class MyQueue{
    public:
        deque<int> q;
        void pop(int val){
            if(!q.empty() && val==q.front())
                q.pop_front();
        }
    
        void push(int val){
            while(!q.empty() && val>q.back())
                q.pop_back();
            q.push_back(val);
        }

        int front(){
            return q.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue q;
        vector<int> res;
        for(int i=0;i<k;i++)
            q.push(nums[i]);
        res.push_back(q.front());
        for(int i=k;i<nums.size();i++){
            q.pop(nums[i-k]);
            q.push(nums[i]);
            res.push_back(q.front());
        }
        return res;
    }
};

LeetCode 347.前K个高频元素【优先队列】

此题的思想是小根堆的实现方式，只不过我们用优先队列来实现，我们把整个元素的次序插入，然后按频次次序从小到大排列，把每次最小的从堆中删除，最后留下K个就是最终的K个高频元素。

class Solution {
public:
    class cmp{
    public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second>b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++)
            map[nums[i]]++;
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pri_que;
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k)
                pri_que.pop();
        }

        vector<int> res(k);
        for(int i=k-1;i>=0;i--){
            res[i]=pri_que.top().first;
            pri_que.pop();
        }
        return res;
    }
};

不仅是算法的实现复杂，思路更是要好好研究。