leetcode_day13

今日内容：

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

239.滑动窗口最大值

考验对于priority_queue数据结构的了解和掌握程度，不过不能当API选手，得知道怎么手写堆，不求随手手撕出大小顶堆，但是得知道大概写法。

关于priority_queue的感性理解

在lc上看见了评论区大佬，关于priority_queue的比喻描述很形象，特引用至此：

单调队列真是一种让人感到五味杂陈的数据结构，它的维护过程更是如此.....就拿此题来说，队头最大，往队尾方向单调......有机会站在队头的老大永远心狠手辣，当它从队尾杀进去的时候，如果它发现这里面没一个够自己打的，它会毫无人性地屠城，把原先队里的人头全部丢出去，转身建立起自己的政权，野心勃勃地准备开创一个新的王朝.....这时候，它的人格竟发生了一百八十度大反转，它变成了一位胸怀宽广的慈父！它热情地请那些新来的“小个子”们入住自己的王国......然而，这些小个子似乎天性都是一样的——嫉妒心强，倘若见到比自己还小的居然更早入住王国，它们会心狠手辣地找一个夜晚把它们通通干掉，好让自己享受更大的“蛋糕”；当然，遇到比自己强大的，它们也没辙，乖乖夹起尾巴做人。像这样的暗杀事件每天都在上演，虽然王国里日益笼罩上白色恐怖，但是好在没有后来者强大到足以干翻国王，江山还算能稳住。直到有一天，闯进来了一位真正厉害的角色，就像当年打江山的国王一样，手段狠辣，野心膨胀，于是又是大屠城......历史总是轮回的。

似乎没办法贴评论的链接，去description下找吧，应该挺靠前的。

叛军屠城 = 遇到新最值，全弹出; 慈悲为怀 = 后续小值有序堆在队头之后;

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> pq;//存pair，得带上值得下标方便确定是不是该出队
        vector<int> ans;
        for(int i = 0;i < nums.size();i++) {
            if(pq.empty()) pq.push(pair(nums[i], i));//空的直接存
            else if(nums[i] >= pq.top().first) {//新最值，全出队
                while(!pq.empty()) pq.pop();
                pq.push(pair(nums[i], i));
            }
            else if(pq.size() >= k) {//已满
                pq.push(pair(nums[i], i));
                while(pq.top().second + k <= i)//出队已经晚了的,注意得是while
                    pq.pop();
            }
            else pq.push(pair(nums[i], i));
            if(i + 1 >= k) ans.push_back(pq.top().first);
        }
        return ans;
    }
};

347.前k个高频元素

感觉思路比较简单暴力，用map来记“值-频率”，然后根据“频率数组”建堆排序来降低时间复杂度到O(nlogn)以下。总之是先记再排序。

不过carl的反其道而行很巧妙，采用小根堆，这样就可以简单地根据队列盈满来出队队头，官解也是小根堆，不过没有简单出队，而是判断当前的和队头的哪个更小，如果队头更小才出队。

对于pq自定义排序标准的语法不了解，是看过之后才写的，对于这道题

priority_queue的模板类型参数有三，1.要存的类型；2.要存的类型的vector；3.自定义比较方法所在类，自定义比较需重载()运算符

代码

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) {
        //用map记录值-频率，通过优先队列或者堆来对前k个频率排序，最后输出前k个元素
        unordered_map<int, int> map;
        for(int i : nums) map[i]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
        for(auto it : map) {
            pq.push(it);
            if(pq.size() > k) pq.pop();
        }
        vector<int> ans;
        while (k--){
            int t = pq.top().first;
            ans.push_back(t);
            pq.pop();
        }
        return ans;
    }
};