代码随想录算法训练营第十三天|239 滑动窗口最大值、347 前K个高频元素

滑动窗口最大值

题目链接：滑动窗口最大值

思路

一种暴力思路就是：遍历所有的滑动窗口，然后找到每一个滑动窗口的最大值，显然这样复杂度为O(n*k)。
之前从没有接触过单调队列（无论何时，队列中的元素是单调的），然后可以手动地重复下过程，这样时间复杂度就变为了O(n)。在本题目中使用单调队列（从大到小），所以窗口内的最大值一直在队列的front。所以我们一直维护的是一个单调队列，那些不符合单调的元素在新元素push时已经被pop掉了，在真正pop时也不需要pop`。
在本题目中一个单调队列需要三个方法pop、push、getMaxValue。

class Solution {
private:
    class MyQueue{
    public:
        deque<int> que; 
        void push(int value){
            while(!que.empty() && value > que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }

        void pop(int value){
            if(!que.empty() && value == que.front()){
                que.pop_front();
            }
        }

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

        res.emplace_back(que.getMaxValue());
        for(int i=k; i<nums.size(); i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.emplace_back(que.getMaxValue());
        }
        return res;
    }
};

347 前k个高频元素(五颗星)

题目链接：前k个高频元素

堆

堆是一种满足特定条件的完全二叉树（满二叉树消减最右边是完全二叉树），主要分为两种类型

• 小顶堆：任意节点的值小于等于其子节点的值
• 大顶堆：任意节点的值大于等于其子节点的值

需要指出的是，许多编程语言 提供的是优先队列priority queue这一抽象数据结构。实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。

思路

想到了一种比较暴力的方法。建一个map，key用来存储元素，value存储元素出现的频率，然后在对value排序，最终返回前k个key即可。
排序如果使用快速排序，则时间复杂度是O(nlogn)。使用优先队列来对频率进行排序，复杂度是O(nlogk)，因为小顶堆中只用维护k个元素。
参考解析后，新的解决方案如下：

1. 使用map存储数据
2. 创建一个大小为k的小顶堆来对map进行排序
3. 返回结果

其中重中之重是使用什么方法进行排序以及小顶堆如何创建。

class Solution {
public:
    // 小顶堆
    class cmp{
    public:
        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) {
        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(auto it:map){
            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;
    }
};

参考链接

1. https://www.hello-algo.com/chapter_heap/heap/
2. https://www.programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF