代码随想录算法训练营第十三天 | 239. 滑动窗口最大值、347.前 K 个高频元素

239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值

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

返回 滑动窗口中的最大值 。

文章讲解/视频讲解：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

思路

设置一个大小为k的队列queue。

在滑动窗口处于初始位置时，将初始的k个元素推入队列中：
如果队列为空或者当前元素小于队列的队尾元素，直接将nums[i]推入队列尾部；
如果当前元素大于队列的队尾元素，则循环判断，只要队列的队尾元素小于当前元素，就将当前队尾排出，直到循环判断结束，将nums[i]推入队列尾部。
此时队列的队首就是当前窗口的最大值。

滑动窗口开始移动时，开始对整数数组nums的后续元素进行遍历：
此时滑动窗口的范围为[i, i + k - 1]，如果nums[i - 1]等于队首元素，则将队首排出，说明此时队首已经不在滑动窗口中了；
对于当前值nums[i]，如果队列为空或nums[i]小于队列的队尾元素，直接将nums[i]推入队列尾部，如果此时队列大小大于k，将队首排出；
如果nums[i]大于队列的队尾元素，则开始循环判断，只要队列的队尾元素小于nums[i]，就将当前队尾排出，直到循环判断结束，将nums[i]推入队列尾部。
同样的，每次遍历，当前队列的队首就是当前窗口的最大值。

上述方法在构建队列时，可以保证队列中的元素是单调非增的，因此队首就是当前窗口的最大值。同时，因为需要对队列的队尾做排出操作，用deque双向队列来作为队列的容器。
注：如果用vector作为容器，会超时。因为排出队首元素是o(n)复杂度的。

C++实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> results;

        deque<int> dQ;

        for(int i = 0;i<k;i++){

            if(dQ.empty() || nums[i] <= dQ.back()){
                dQ.push_back(nums[i]);
            }
            else{
                while(!dQ.empty() && dQ.back() < nums[i]) dQ.pop_back();
                dQ.push_back(nums[i]);
            }
        }

        results.push_back(dQ.front());

        for(int i = k;i<nums.size();i++){
            if(nums[i - k] == dQ.front()) dQ.pop_front();
            if(dQ.empty() || nums[i] <= dQ.back()){
                dQ.push_back(nums[i]);
                if(dQ.size() > k) dQ.pop_front();
            }
            else{
                while(!dQ.empty() && dQ.back() < nums[i]) dQ.pop_back();
                dQ.push_back(nums[i]);
            }
            results.push_back(dQ.front());
        }

        return results;
    }
};

347.前 K 个高频元素

题目链接：347.前 K 个高频元素

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

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

思路

用小顶堆来实现。
定义一种node结构，属性分别为值和频率。
首先遍历数组，统计每个元素的出现频率，将代表每个元素的node存入数组frequents。
定义一个存储node类型的小顶堆，堆的判断标准是node之间的频率，频率越低越靠前。
遍历数组frequents，将元素不断地push进这个小顶堆中，如果小顶堆的大小大于k，则将小顶堆的堆顶排出。

最终小顶堆中的所有元素，构成了前K个高频元素。

C++实现

struct node{
    int value;
    int frequence;
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        auto cmp = [](node a, node b){return a.frequence > b.frequence;};
        priority_queue<node, vector<node>, decltype(cmp)> Q(cmp);

        vector<node> frequents;
        unordered_map<int, int> hashMap;
        for(int i = 0;i<nums.size();i++){
            hashMap[nums[i]] += 1;
        }
        for(auto p : hashMap){
            frequents.push_back({p.first, p.second});
        }

        for(int i = 0;i<frequents.size();i++){
            Q.push(frequents[i]);
            if(Q.size() > k) Q.pop();
        }

        vector<int> results;
        while(!Q.empty()){
            results.push_back(Q.top().value);
            Q.pop();
        }
        return results;
    }
};