每日二题(滑动窗口max、前k个高频元素)

239. 滑动窗口最大值

力扣题目链接(opens new window)

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

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

347.前 K 个高频元素

力扣题目链接(opens new window)

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

• 输入: nums = [1,1,1,2,2,3], k = 2
• 输出: [1,2]

示例 2:

• 输入: nums = [1], k = 1
• 输出: [1]

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

//
// Created by 徐昊岩 on 2023/11/22.
//
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        queue<int> que;
        vector<int> k_max;
        for(int i=0;i<k;i++){
            que.emplace(nums[i]);
            while(que.front()<nums[i]){
                que.pop();
            }
        }
        res.push_back(que.front());
        for(int i=k;i<nums.size();i++){
            que.emplace(nums[i]);
            if(que.size()>k) {
                que.pop();
                int max=INT32_MIN;
                int wei=0;
                for(int o=i-k+1;o<i-k+1+k;o++){
                    if(max<nums[o]){
                        max=nums[o];
                        wei=o-(i-k+1);
                    }
                }
                while(wei>0){
                    que.pop();
                    wei--;
                }

            }
            while(que.front()<nums[i]){
                que.pop();
            }
            res.push_back(que.front());

        }
        return res;

    }

};
class Solution2 {
    class myQueue{  //用deq构造一个专门存储第一大、第二大、第三大......的队列
        deque<int> deq;
    public:
        void pop(){
            deq.pop_front();
        }
        void push(int a){
            while (!deq.empty()&&a>deq.back()){
                deq.pop_back();
            }
            deq.push_back(a);
        }
        int front(){
            return deq.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        myQueue myq;
        for(int i=0;i<k;i++){
            myq.push(nums[i]);
        }
        res.push_back(myq.front());
        for(int i=k;i<nums.size();i++){
            if(nums[i-k]==myq.front()){
                myq.pop();
            }
            myq.push(nums[i]);
            res.push_back(myq.front());
        }
        return res;
    }
};

class Solution3 {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        multimap<int,int> multimap1;   //！！注意不要将变量起名为multimap原名，会影响后续创建变量！！！
        multimap<int,int> multimap2;
        vector<int> res;
        for(int a:nums){
            auto it=multimap1.find(a);
            if(it==multimap1.end()) multimap1.emplace(a,1);
            else{
                it->second++;
            }
        }
        int temp;
        for(pair<int,int> pair:multimap1){
            multimap2.emplace(pair.second,pair.first);
        }
        for(auto item=--multimap2.end();k>0;item--){  //以另一个元素作为循环时，要注意增减顺序，防止超过范围
            res.push_back(item->second);
            k--;
        }
        return res;
    }
};