代码随想录算法训练营第13天 |第五章 栈与队列part03

学习目标：

• 239. 滑动窗口最大值 （一刷至少需要理解思路）
• 347.前 K 个高频元素

---

学习内容：

239. 滑动窗口最大值

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);

            }
            
            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++)
        {
            que.push(nums[i]); // 先将前k个元素放进队列
        }
        result.push_back(que.front());//记录这前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
49
50

错误以及注意事项

• 这个题，看了视频以及对应的解析，还是不太理解。
• 在这段代码中，MyQueue 类是一个用于维护单调队列的辅助类。在 pop 操作中，作者使用了条件判断 if (!que.empty() && value == que.front())，这是为了确保在弹出元素时，只有当要弹出的值等于队列的前端元素值时才执行弹出操作。这是因为在滑动窗口的过程中，可能存在之前的最大值仍然存在于队列中，但已经不在当前滑动窗口的范围内，因此需要在弹出操作时检查值是否相等，以避免错误地将当前窗口范围之外的值弹出。

在这个实现中，pop 操作是在滑动窗口的过程中移除最前面的元素，因此需要确保移除的元素是当前窗口范围内的元素，而不是之前的最大值。通过检查值是否相等，可以避免错误地将不属于当前窗口的元素从队列中移除。

347.前 K 个高频元素

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;
        for(int i = 0;i<nums.size();i++)
        {
            map[nums[i]]++;
        }

        //对频率排序
        //定义一个小顶堆,这个小顶堆是怎么这样做的
        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)
            {
                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

错误以及注意事项

• 在这个代码中，通过定义了 mycomparison 类，实现了一个小顶堆。小顶堆是通过优先队列 priority_queue 实现的，其中使用了自定义的比较器 mycomparison。首先，mycomparison 类定义了一个函数调用运算符 operator()，用于比较两个 pair<int, int> 对。在这里，比较的依据是 pair 的第二个元素，即频率，使用 lhs.second > rhs.second 来确保构建的是小顶堆，即频率小的元素优先级高。

学习时间：

2023.12.11 20:00-21:20
眼睛好痛。