栈和队列(三)|239.滑动窗口最大值、347.前K个高频元素-创新互联

239. 滑动窗口大值

题意理解:本题因为要求时间复杂度是线性O(n),所以不能采用暴力解法O(k*n),也就是对所有的窗口元素遍历求大值输出。

网站建设哪家好,找成都创新互联!专注于网页设计、网站建设、微信开发、小程序定制开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了君山免费建站欢迎大家使用!

卡哥采用了自己定义单调栈的方法,实现在滑动窗口移动的pop和push过程中就对栈内元素进行维护,使得栈首永远保存窗口大值。

该栈的实现基于deque,因为它也是queue的底层,而且可以方便地对首端尾端进行删除和填入的操作,便于DIY。

步骤:

  • 定义自己的单调栈和pop,push,front方法

  • 注意pop和push带参数value,这是区别于常规的特点。并且自己的pop和push方法分别是在首端pop,尾端push。

  • push时,栈尾部比value小,就要被持续地卷走

  • pop时,栈首若等于value,就被pop掉,否则不需要操作,因为已经在push时被卷走了

  • front就是获取栈首值,直接返回就好,因为我们在pop和push时已经维护了栈首即为滑动窗口大值

  • 平台调用方法maxSlidingWindow,记得先把前k个值塞进栈里再进入读数组数据的循环。记得实体化声明我们的单调栈

本题关键收获:

  • 实现自己用deque去DIY栈

  • 在栈内进行数据维护

  • 在类内同样可以实现一个类

class Solution {
public:
    class myqueue{
        public:
            dequeque;
            void push(int value){
                // 新进来的值比栈尾数据大就从尾部弹出
                while(!que.empty()&&que.back()maxSlidingWindow(vector& nums, int k) {
        myqueue que;
        // 把前k个数据先放进栈里,并生成第一个滑动窗口的大值
        for(int i=0;ires;
        res.push_back(que.front());
        // 开始push pop操作,并即时更新滑动窗口大值
        for(int i = k;i
347. 前 K 个高频元素

题意理解:

首先需要统计各元素出现的频率,用unordered_map是很好的。

其次本题是要求前k个高频元素,所以没必要对所有的map成员进行排序,只需要维护前k个成员即可,这时候用小顶堆很好,而优先级队列priority_queue就是基于小顶堆实现的,小顶堆也是一种二叉树。

最后对维护好的优先级队列转换成vector输出结果,注意顺序

步骤:

  • 统计各元素出现频率

  • 定义优先级队列(排列规则compare函数要自己写)

  • 遍历map成员输入到优先级队列中,并且当队列元素超过k时弹出,小顶堆的顶是小元素

  • 输出到结果vector中

本题收获:

重点掌握小顶堆和优先级队列的应用场景,对于本题只需要维护前k个高频元素的情况很适用

要学会写自己的仿函数compare

学会声明优先级队列

掌握对map元素遍历的方法 ,采用迭代器

class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair& lhs, const pair& rhs) {
            return lhs.second >rhs.second;
        }
    };
    vectortopKFrequent(vector& nums, int k) {
        // 统计各元素出现次数
        unordered_mapmap;
        for(int i=0;i, vector>, mycomparison>que;
        for(auto it=map.begin();it!=map.end();it++){
            que.push(*it);
            if(que.size()>k) que.pop();
        }

        vectorres(k);
        for(int i=k-1;i>=0;i--){
            res[i] = que.top().first; // first是属性不是方法
            que.pop();
        }
        return res;
    }
};

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


本文名称:栈和队列(三)|239.滑动窗口最大值、347.前K个高频元素-创新互联
网址分享:http://myzitong.com/article/dehdpo.html