栈和队列（三）|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个高频元素-创新互联
网站URL：https://www.cdcxhl.com/article30/dehdpo.html

成都网站建设公司_创新互联，为您提供小程序开发、做网站、软件开发、网站制作、搜索引擎优化、全网营销推广

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站优化排名

用户体验知识

行业网站建设