当前位置: 首页 > news >正文

栈与队列专题

力扣239题  滑动窗口最大值

设计单调队列的时候,pop和push操作要保持如下规则:

1.pop(value):如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作

2.push(value):如果push的元素value大于入口元素的数值,那么就将队列入口的元素弹出,直到push元素的数值小于等于队列入口元素的数值为止。

class MyQueue { //单调队列(从大到小)
public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}
};


完整的代码逻辑:
class Solution {
public:
    class MyQueue{
    public:
        deque<int>que;
        void pop(int value){
            if(!que.empty()&&value == que.front()){
                que.pop_front();
            }
        }

        void push(int value){
            while(!que.empty()&&value > que.back()){
                que.pop_back();
            }
            que.push_back(value);
        }
        int front(){
            return que.front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int>result;
        for(int i=0;i<k;i++){
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i=k;i<nums.size();i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};
 
 
力扣347题 前K个高频元素
这道题目主要涉及到如下三块内容
1.要统计元素出现频率
2.对频率排序
3.找出前k个高频元素
优先级队列对外接口只是从队头取元素,从队尾添加元素,再无其他取元素的方法,看起来就是一个队列。 
堆是一颗完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。
只排序k个元素,要用小顶堆,因为要统计最大前k个元素,只有小顶堆每次将最小的元素弹出,最后小顶堆里积累的才是前k个最大元素。
 
class Solution {
public:
    class mycomparison{
    public:
       bool operator()(const pair<int,int>&lhs,const pair<int,int>&rhs){
           return lhs.second > rhs.second;
       }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>map;
        for(int i=0;i<nums.size();i++){
            map[nums[i]];
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pri_que;

        for(unordered_map<int,int>::iterator it = map.begin();it !=map.end();it++){
            pri_que.push(*it);
            if(pri_que.size()>k){
                pri_que.pop();
            }
        }

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


























http://www.hskmm.com/?act=detail&tid=15847

相关文章:

  • 读书笔记:为什么你的索引“罢工”了?六种常见原因解析
  • 平面网格材质
  • OSCP备考成功指南:9大实用学习技巧
  • 设备租赁系统:建材租赁行业的高效管理解决方案
  • NOI 2025 题解
  • 迈特海外短剧多语言版 SAAS 开源系统:助力短剧出海,开启全球盈利新赛道
  • 临时测试php文件
  • csv文件中的空行问题
  • 直播点播会议一体,EasyDSS如何用一个平台解决企业所有视频难题?
  • 在 C++ 中实现反射机制并不一定必须使用宏
  • 在CodeBolcks下wxSmith的C++编程教程——使用多个表单(多窗口程序)
  • Windows下Tesseract-OCR的安装与使用
  • 学习 React 前,你必须掌握的 10 个 JavaScript 核心概念
  • 二维下标极大数组(二维 map)
  • PySide6 之自定义弹出框
  • CF932E Team Work
  • HTTP3与HTTP2的性能对比
  • KubeSphere 社区版即将发布:开启云原生新篇章
  • 答题互动网页收藏
  • 芯脉:面向高速接口的SoC架构与完整性设计<3> - 教程
  • vscode插件开发,打包后不生效问题解决
  • streamlit构建dashboard
  • 力扣 338题 比特位计数
  • 企业服务管理是做什么的?-ManageEngine卓豪
  • 学习笔记_在Python中使用微信扫码功能(OpenCV WeChatQRCode)
  • 国标GB28181视频平台EasyCVR如何构建安防监控“中枢神经”?
  • vscode中element-plus组件无属性提示
  • day07
  • minio集群搭建
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名餐饮菜谱应用需求洞察