代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素

本文主要是介绍代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

239. 滑动窗口最大值

思路:
用遍历区间的元素时,维护一个单调队列,从大到小排列。
要找到最大值,实际单调队列保存区间内最大值及最大值右侧的第二大值(用于当前最大值处于区间左端,在区间右移时更新临时最大值,只需要用临时最大值和新区间右端元素比较就可以知道新的最大元素)。为什么强调是最大值右侧的第二大值,因为最大值左侧的元素必然在最大值前离开区间。
特殊情况:

代码实现

class Solution {
private:class Myqueue{public:deque<int> que;// 使用deque来实现单调队列// 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int num){if(!que.empty() && num == que.front()){que.pop_front();}}// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int num){while(!que.empty() && num > que.back()){que.pop_back();}que.push_back(num);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front(){return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> maxNum;Myqueue que;int temp = 0;for(int left = 0, right = k-1; right < nums.size(); left++, right++){//实际temp遍历nums每个元素,且每个元素只遍历到一次while(temp <= right){que.push(nums[temp]);temp++;}maxNum.push_back(que.front());que.pop(nums[left]);}return maxNum;}
};

347.前 K 个高频元素

思路:

  1. 用unordered_map 保存元素出现频率
  2. 使用优先队列的小顶堆 最小的元素最优先出队(自定义数据结构,重定义排序规则)

特殊情况:

class Solution {
public://自定义数据结构,重定义排序规则class mycmp{public:bool operator()(const pair<int, int> &lfs, const pair<int, int> &rfs){return lfs.second > rfs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {//用unordered_map 保存元素出现频率unordered_map<int,int> Map;for(int num : nums){Map[num]++;}//使用优先队列的小顶堆  最小的元素最优先出队priority_queue<pair<int,int>, vector<pair<int, int>>, mycmp> pri_que;for(auto p : Map){pri_que.push(p);if(pri_que.size()>k) pri_que.pop();}vector<int> result(k);for(int i = result.size()-1; i >= 0; i--){result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

这篇关于代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/637797

相关文章

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.