代码随想录算法训练营 Day13 栈与队列part03 ● 239. 滑动窗口最大值● 347.前 K 个高频元素● 总结

239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）

文章链接：代码随想录 (programmercarl.com)

视频链接：单调队列正式登场！| LeetCode：239. 滑动窗口最大值

这道题比较困难，我看来代码许久，才搞明白究竟啥意思。

首先奉上思路，这道题我的第一想法就是“暴力出奇迹” ，但不出意外的超时了。通过卡哥的代码，学习到还可以使用“单调队列”解决这道题。

单调队列的意思就是通过滑动窗口，让元素通过或出队列，并保持单调递增或递减的形式。而在C++中并没有这样现成数据结构给我们，所以要构造。自定义pop，push

总代码如下：

class Solution {
    private:
    class myqueue
    {
        public:
        deque<int> que;
        void pop(int value)//从队列前方依次删除元素
        {
            if(que.empty()==false&&value==que.front())
            {
                que.pop_front();
            }
        }
        void push(int value)//从队列后插入元素，小于该元素的就移除
        {
            while(que.empty()==false&&que.back()<value)
            {
                que.pop_back();
            }
            que.push_back(value);
        }
        int max()//队列呈单调递减，front就是最大的
        {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        myqueue que;
        for(int i=0;i<k;i++)
        {
            que.push(nums[i]);
        }
        result.push_back(que.max());
        for(int i=k;i<nums.size();i++)
        {
            que.push(nums[i]);
            que.pop(nums[i-k]);//和自定义pop函数对照看，理解if语句中有value==que.front()可能被push全部移除了，就不存在原来的头元素
            result.push_back(que.max());
        } 
       return result;
    }
};

这道题难点就在自定义单调队列，需要充分理解deque，很有难度，可以多加思考。

347.前 K 个高频元素

 题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）

文章链接：代码随想录 (programmercarl.com)

视频链接：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素

这道题主要运用的map、大堆顶、小堆顶和优先级队列的知识 

这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率——map哈希表
2. 对频率排序——一个dor循环反向输出
3. 找出前K个高频元素——优先级队列，小堆顶

对于优先级队列、大堆顶、小堆顶，我也是第一次接触，在此说一下自己的看法。

优先级队列已经不满足普通队列的先进先出的条件了，每次出的都是优先级最大的元素，而优先级又是自己通过元素的大小来定义的。

定义如下：

priority_queue<typename, container, functional>

typename是数据的类型；

container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；

functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

总代码如下：

class Solution {
public:
    class mycomparison{
        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> umap;//map记录每个元素的频率
        for(int i=0;i<nums.size();i++)
        {
            umap[nums[i]]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pri_que;//优先级队列的定义
        for(unordered_map<int,int>::iterator it=umap.begin();it!=umap.end();it++)//map遍历插入队列中
        {
            pri_que.push(*it);
            if(pri_que.size()>k)
            {
                pri_que.pop();
            }
        }
        vector<int> result(k);
        for(int i=k-1;i>=0;i--)
        {
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

总结

代码随想录 (programmercarl.com)

今天主要就是把这两道题了解了下思路，自己尝试写了写代码，由于deque、优先级队列、大顶堆小顶堆都是第一次接触，很是生疏，共花了3个小时。

Day13打卡成功，再接再厉