239滑动窗口最大值&347前K个高频元素

class MyQueue{ //单调队列（从大到小
public:
    deque<int> que; //使用deque实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等就弹出
    // 同时pop之前判断队列当前是否为空
    void pop( int value){
        if( !que.empty() && value ==  que.front()){
            que.pop_front();
        }
    }

    // 如果push的数值＞入口元素的数值，就讲队列后端的数值弹出，直到push的数值＜等于队列入口元素的数值为止
    // 保证队列的数值是从大到小的。
    void push( int value) {
        while(!que.empty()&& value > que.back()){
            que.pop_back();//弹出队列尾部元素
        }
        que.push_back(value);
    }

    // 查询当前队列里的最大值，直接返回队列前端也就是front就可以了。
    int front(){
        return que.front();
    }
};


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i< k; i++){ //先将前K个元素放进队列
            que.push(nums[i]);
        }

        result.push_back(que.front()); //result记录前k个元素的最大值。

        for( int i = k ; i < nums.size(); i++){
            que.pop(nums[i-k]); //滑动窗口移除最前面的元素
            que.push(nums[i]); //滑动窗口前加入最后面的元素
            result.push_back(que.front()); //记录对应的最大值
        }
        return result;
    }
};

// 还是没怎么看懂代码 稍微有点复杂
class Solution {
public:
    // 定义小顶堆
    class mycomparison{
    public:
        // pair<int,int>用来创建对组，first表示第一个数，second表示第二个数
        bool operator()( const pair<int,int>& lhs,const pair<int,int>& rhs){
            return lhs.second > rhs.second;
    }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 时间复杂度 O(nlogk)
        // 空间复杂度 O(n)

        // 统计元素出现的概率
        unordered_map<int,int> map; //统计元素对应出现的次数
        for( int i = 0 ; i < nums.size(); i++){
            map[nums[i]]++;
        }
        // 对频率排序
        // 定义小顶堆，大小为k 优先队列
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pri_que;
        // 用固定大小为k的小顶堆，扫描所有数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
            }
        vector<int> resutl(k);
        for( int i = k - 1; i >= 0;i--){
            resutl[i] = pri_que.top().first;
            pri_que.pop();
        }
        return resutl;
    }
};