【算法练习Day11】滑动窗口最大值&&前 K 个高频元素

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

这道题是一道困难题，给出一个滑动窗口的长度，给出一个数组，每次滑动窗口向数组右侧滑动一个元素，要求返回一个数组该数组记录的是每次移动滑动窗口所包含的数字中最大的一个分别是什么。
不难想出暴力解法，每移动一次遍历一遍窗口记录下来当前最大的数，时间复杂度是n*k，一共n个数据，要遍历k次。那么有没有更好的方法来节省时间呢？这时我们的单调队列要登场了！

什么是单调队列？

单调队列是单调递增的队列或者单调递减的队列，但是它和优先级队列的不同之处在于，我们设计它的时候主要是要维护大值或者小值而单调递增或递减的排序是进出元素控制的并非主要思路是排序，这和优先级队列的区别还是很大的，顺便说一下单调队列通常使用双端队列做模板实现，而优先级队列底层实现是堆，也就是二叉树。
本题我们可以借助双端队列创建一个单调队列，因为c++里没有现成的单调队列，单调队列只需要三个函数，一个push一个pop一个求最大值

我们如何每次都弹出最大值呢？

其实只是需要我们将最大值调整到队列口处，而前面小的数直接pop走，其实我们要求的是每次窗口中的最大值，所以小数完全没有必要维护，直接判断弹出即可，push时我们判断队尾有没有数小于要push进来的数，如果有全部pop出来，因为是在队尾插入所以要对对尾元素做判断，在实现pop函数时判断本次要删除的元素队头有没有，没有就不删（没有的原因是之前push元素时候已经弹出了，因为为了保证取最大值的函数每次都取最大）一开始直接push前k个元素，之后采取push一个元素pop一个元素的规律，值得注意的，不是每一次都要pop，但是每一次都要调用，至于具体这一步是否真的pop了在pop函数会自动判断。

为什么会这样呢？

原因在于我们设计的单调函数里实现的时候我们需要照顾到弹出最大值这个函数，所以我们设计成这样用来方便最大值的弹出，而在真正函数调用时候，为了保证逻辑上的正确，我们每次都要调用pop这个函数，判断如果此时我们要删的元素不在队头部，那么直接往后走加入新元素即可。

class Solution {
private:
    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();
        }
    };
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

时间复杂度: O(n)
空间复杂度: O(k)

前 K 个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）
这道题是考察优先级队列和语法理解

这道题是一个输出前k个高频元素的题，并不是只输出一个。所以我们想到用优先级队列来存取前k个高频元素

那么如何判断哪些是高频元素呢?

我们用unordered_map来存取每个数据出现的次数，然后用小顶堆来存取数据。

为什么要用小顶堆而不是大顶堆？

我们的思路是定义一个只能存k个元素的堆，这样我们只需要维护k个数据，减少不必要的浪费。由于哈希存储结果是unordered_map来提高效率，所以map里是无序的，我们在插入元素时候要按着map依次插入进去，而用大顶堆的话，大的数据排在前面如果map里还有更大的数据，那么之前最大的数据要先被弹出来，往复操作最后只剩下频率最低的k个元素。而使用小顶堆那么每次弹出最小元素，加进来较大元素，最后沉淀下来的是k个高频数据。当然如果使用的是map的话可能就不需要考虑这些问题，因为是排好序的。

按着刚才的思路写出代码

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> map; // 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();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) 
        {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

注意:把map的两个数据都放到堆里，然后根据二元组的第二个关键词来进行排序，这样我们在进行最后一步转化为数组的时候，才能根据频率找到对应的数据，缺一不可

总结

今天我们完成了滑动窗口最大值、前 K 个高频元素两道题目，相关的思想需要多复习回顾。接下来，我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~