Day12|239.滑动窗口最大值|347.前K个高频元素-创新互联

239. 滑动窗口大值

注意点：

1.确定一个双头队列deque

2.将滑动窗口的大值放到deque的最前面--front函数；如果滑动窗口往右移动，删除的值将和queue的front进行比较，如果相同，则弹出--pop函数；滑动窗口右移，新增加的数字将与queue中的数字进行比较，采用单增序列进行排列，将小的全删除了

3.push_back()函数是链表（vector string deque）的成员函数，push（） 函数是栈Stack的成员函数

class Solution {
private:
    class MyQueue{
        public:
        dequeque;
    // 每次弹出的时候和que队列出口元素进行对比，如果相同则弹出
        void pop(int value) {
            if(!que.empty() && value == que.front())
                que.pop_front();
        }
    // 将value压入到队列中，value与队列中的元素比较，将值放到相应的位置，比value小的数值直接丢弃
        void push(int value) {
            while(!que.empty() && value >que.back())
                que.pop_back();
            que.push_back(value);
        }
// 获得大值
        int front(){
            return que.front();
        }

    };
public:
    vectormaxSlidingWindow(vector& nums, int k) {
        MyQueue que;
        vectorresult;
        for(int i =0; i

347. 前 K 个高频元素

注意点：

1.优先队列需要三个参数，第一个参数是数据类型，第二个队列是数据容器，第三个是排序方式

//升序队列，头部是最小的元素，即小顶堆
priority_queue,greater>q;
//降序队列，头部是大的元素，即小顶堆
priority_queue,less>q;

2. >表示右边的大，是降序排列

3.采用小堆顶进行统计前k个元素的个数

4.因为小堆顶采用最小次数的元素出现在小堆顶的堆顶，在进行最后的输出的时候，进行倒序输出

class Solution {
public:
    // 小堆顶
    class mycomparision {
        public:
            bool operator()(const pair& lhs, const pair& rhs) {
                return lhs.second >rhs.second;//>表示右边的大，是降序排列
            }

    };
    vectortopKFrequent(vector& nums, int k) {
        unordered_mapmap;//key是元素 value是出现的次数
        for(int i = 0; i< nums.size(); i++) {
            map[nums[i]]++;
        }
// 优先队列需要三个参数，第一个参数是数据类型，第二个队列是数据容器，第三个是排序方式
        priority_queue, vector>, mycomparision>pri_que;
        for(auto it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);//it包含if(pri_que.size() >k)
                pri_que.pop();
        }

        vectorresult(k);
        for(int i = k-1; i>= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧