第12天-代码随想录刷题训练-第五章 栈和队列3 - ● 239. 滑动窗口最大值 ● 347.前 K 个高频元素

今天主要是队列的应用

1. 滑动窗口最大值 (困难-单调队列)

LeetCode 原题

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值

• 思路
  • 暴力方法，每次遍历窗口内的数据,遍历(n-k 1)次,时间复杂度为 k*n
  • 滑动窗口的过程很像是一个队列, 每次遍历一个元素都要 pop一个元素, push一个元素, 最后再getMax
  • 因此这是一个优先级队列，C 中相当于实现一个 大顶堆, 头部元素是最大值, 底层由二叉树实现，但是顶部元素是最大值，每次都是pop最大值
  • 综上本文要实现的应该是一个单调队列: 队列中只存储当前最大值(作为队列头元素)和最大值之后的元素，最大值之前的元素全部pop掉，对本题的求窗口内最大值并没有帮助
  • 考虑到本题需要在两端对队列进行操作，因此使用deque数据结构
  • pop_q(val): 判断deque是否为空, front()与val是否相等,是则pop()
  • push_q(val): push的时候,先判断是否为空与back()的元素比大小,如果一直大于back()的元素则一直pop_back()

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> maxResult;
        int max;
        for(int i=0; i<k; i  ){
            push_back(nums[i]);
        }
        max = getMaxVal();
        maxResult.push_back(max);

        for(int i=k; i<nums.size(); i  ){
            pop_front(nums[i-k]);
            push_back(nums[i]);
            max = getMaxVal();
            maxResult.push_back(max);
        }

        return maxResult;
        
    }

    void push_back(int val){
        while(!dq.empty() && val>dq.back()){
            dq.pop_back();  
        }
        dq.push_back(val);
    }

    void pop_front(int val){
        if(!dq.empty() && dq.front()==val){
            dq.pop_front();
        }
    }

    int getMaxVal(){
        int result;
        if(!dq.empty()){
            result = dq.front();
        }

        return result;
    }

private:
    deque<int> dq;
};

2.前 K 个高频元素 (大顶堆 和 小顶堆)

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

• 思路
  • 遍历一遍数组，使用map存储 key元素值 和val出现的次数
  • 使用大顶堆还是小顶堆， 由于顶堆这个数据结构每次都弹出顶部元素，如果使用val排序的大顶堆，每次会将出现频率大的值都给弹出来，因此应该使用小顶堆
  • C 中的 大顶堆/小顶堆 数据结构 priority_queue
  • 优先级队列中存储的是 pair<k, v> 值， 然后自定义Compare函数来定义小顶堆
• 基础
  • 树形结构使用迭代器遍历?
  • priority_queue 的Compare函数
  • priority_queue要自定义Compare函数就需要定义第二个参数，底层实现的容器 vector deque list
  • 优先级队列的 Compare函数 left > right 是小顶堆, left < right 是大顶堆
  • 使用lambda函数的时候需要注意 使用方式

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) {
        // 使用优先级队列实现 小顶堆
        // map存储元素的值和出现的次数
        unordered_map<int, int> m;
        for(auto num : nums){
            m[num]  ;
        }

        // priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
        auto compar = [](pair<int, int>& lhs, pair<int, int>& rhs){ return lhs.second > rhs.second;};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compar)> pq(compar);

        // priority_queue 有size()函数
        for(unordered_map<int, int>::iterator im = m.begin(); im != m.end(); im  ){
            pq.push(*im);

            if(pq.size() > k){
                pq.pop();
            }
        }

        vector<int> result; 
        // 不能使用迭代器访问树结构
        for(int i=0; i<k; i  ){
            int num = pq.top().first;
            pq.pop();
            result.push_back(num);
        }

        return result;
    }
};

这篇好文章是转载于：学新通技术网