算法刷题 Day 13 | 239. 滑动窗口最大值 347.前 K 个高频元素

今日内容：

• 滑动窗口最大值
• 前 K 个高频元素
• 总结

详细布置

239. 滑动窗口最大值 （一刷至少需要理解思路）

之前讲的都是栈的应用，这次该是队列的应用了。

本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

Tips：首先是一个简单的暴力法实现，时间复杂度为O(n × k)，但是这个方法会在一个很大的测试用例下超时

我的题解：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 暴力解法
        vector<int> result;
        for(int i = 0; i + k - 1 < nums.size(); i++){
            int max = INT_MIN;
            if(k == 1){
                max = nums[i] > max ? nums[i] : max;
            }
            else{
                for(int j = 0; j < k - 1; j++){
                    int tempMax = nums[i + j] > nums[i+j+1] ? nums[i+j] : nums[i+j+1];
                    max = tempMax > max ? tempMax : max;
                }
            }
            result.push_back(max);
        }
        return result;
    }
};

Tips：然后就是本题正解单调队列法了，这里要注意，本题中的单调队列是使用STL中的deque实现的。

我的题解：

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 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.front());
        for(int i = k; i < nums.size() ; i++){
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

347.前 K 个高频元素 （一刷至少需要理解思路）

大/小顶堆的应用， 在C++中就是优先级队列

本题是 大数据中取前k值 的经典思路，了解想法之后，不算难。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

Tips：这个题解目前还是照着卡哥的代码敲出来的，主要还是对C++里面的一些写法不太熟悉，这道题需要记忆的点有：

1. unordered_map

2. 优先队列（默认大顶堆，如果需要小顶堆的话需要自己传入一个比较方法）的定义方法：priority_queue<Type, Container, Functional>Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

3. 访问map中元素的时候用迭代器，迭代器类似于指针，前面加*才是指向迭代器指向的元素。

我的题解：

class Solution {
public:
    class mycompare{
    public:
        bool operator()(const pair<int,int>& left, const pair<int,int>& right){
            // 小顶堆
            return left.second > right.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]]++;
        }

        // 定义一个小顶堆，大小为k
        priority_queue<pair<int,int>, vector<pair<int,int>>,mycompare> que;

        for(unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++){
            que.push(*it);
            if(que.size() > k){
                que.pop();
            }
        }

        vector<int> result;
        for(int i = 0; i< k;i++){
            result.push_back(que.top().first);
            que.pop();
        }
        return result;
    }
};

总结

栈与队列做一个总结吧，加油

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html