day13 滑动窗口最大值 前K个高频元素
题目1:239 滑动窗口最大值
题目链接:239 滑动窗口最大值
题意
长度为K的滑动窗口从整数数组的最左侧移动到最右侧,每次只移动1位,求滑动窗口中的最大值
不能使用优先级队列,如果使用大顶堆,最终要pop的元素不知道是哪一个,因为大顶堆已经对队列中的元素进行排序了,元素的顺序发生了改变

暴力解法
对窗口内的所有元素进行排序

单调队列
由于窗口每次只移动1步,所以每真正push一次,就收集一次最大值即可,最大值放到队列的出口
队列只维护窗口中的最大值即可,且队列里的元素是从左到右依次递减的
pop():若滑动窗口原本要移除的元素(val)就是单调队列的出口(front)元素(滑动窗口的最大值),那么就弹出元素
push():如果要放入的元素(val)大于入口(back)的元素,就将入口处(back)小于val的元素逐个卷走,元素再在入口处(back)处入栈
getmaxvalue():每次移动窗口时,队列出口处(front())的元素即为当前窗口的最大值

伪代码

逻辑
例1:前一个滑动窗口删除的元素会不会影响后一个滑动窗口?

代码
class Solution {
private:class MyQueue{public:deque<int> que;//双向队列void pop(int val){if(!que.empty()&&que.front()==val){que.pop_front();}}void push(int val){//去掉入口处比其小的元素while(!que.empty()&&que.back()<val){que.pop_back();}que.push_back(val);}int getmaxvalue(){return que.front();}};
public: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.getmaxvalue());for(int i=k;i<nums.size();i++){//先弹出元素,因为窗口的大小是一定的,只能先弹出元素,再放入元素que.pop(nums[i-k]);//再放入元素que.push(nums[i]);//求最大值result.push_back(que.getmaxvalue());}return result;}
};
- 时间复杂度: O(n)
- 空间复杂度: O(k)
题目2:347 前K个高频元素
题目链接:347 前K个高频元素
题意
返回整数数组nums中出现频率前k高的元素
暴力解法
使用map数组,元素是key,频率是value,然后将value从大到小排序,输出前k个元素(所有元素进行排序)

优先级队列(小顶堆)
为了优化时间复杂度,可以只维护k个元素,没有必要排序所有元素,想到使用优先级队列。
大顶堆,小顶堆擅长求解在大数据集内求排名靠前的元素,堆的底层实现是二叉树
那么使用大顶堆还是使用小顶堆呢?
如果使用大顶堆,那么加入该元素时,弹出最大值,不符题意
如果使用小顶堆,那么加入该元素时,弹出最小值,符合题意,所以,使用小顶堆
使用优先级队列实现大顶堆的话,cmopare函数从大到小排,实现小顶堆的话,compare函数从小到大排

伪代码

代码
class Solution {
public:class mycomparision{public:bool operator()(const pair<int,int>& kv1,const pair<int,int>& kv2){return kv1.second > kv2.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>>,mycomparision> que;//pair<int,int>表示键值对的数据类型<元素(int),频率(int)>//vector<pair<int,int>>表示vector作为que的底层容器,存储元素//遍历map中的元素,小顶堆只维护前k个高频元素for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){que.push(*it);//*it代表迭代器it指向的key-value键值对if(que.size()>k){que.pop();//弹出当前小顶堆中的最小值}}//将小顶堆中频率排名前k的key元素按照频率从高到低放到数组中vector<int> result(k);//这里一定要定义result的大小,因为后续是对result的下标位置进行操作for(int i=k-1;i>=0;i--){result[i] = que.top().first;que.pop();}return result;}
};
- 时间复杂度: O(nlogk)
- 空间复杂度: O(n)
逻辑
例1:最后将堆中的元素放入到数组中时,如果写出这样
vector<int> result;
会报如下错误

原因就是还未给result数组分配内存空间,所以访问result[i]时出错,相当于访问了一个空的空间,和访问空指针差不多一个意思。
相关文章:
day13 滑动窗口最大值 前K个高频元素
题目1:239 滑动窗口最大值 题目链接:239 滑动窗口最大值 题意 长度为K的滑动窗口从整数数组的最左侧移动到最右侧,每次只移动1位,求滑动窗口中的最大值 不能使用优先级队列,如果使用大顶堆,最终要pop的…...
Unity——VContainer的依赖注入
一、IOC控制反转和DI依赖倒置 1、IOC框架核心原理是依赖倒置原则 C#设计模式的六大原则 使用这种思想方式,可以让我们无需关心对象的生成方式,只需要告诉容器我需要的对象即可,而告诉容器我需要对象的方式就叫做DI(依赖注入&…...
【面试突击】Spring 面试实战
🌈🌈🌈🌈🌈🌈🌈🌈 欢迎关注公众号(通过文章导读关注:【11来了】),及时收到 AI 前沿项目工具及新技术 的推送 发送 资料 可领取 深入理…...
【Linux】Ubuntu 22.04 上安装最新版 Nextcloud Hub 7 (28.0.1)
在 Ubuntu 22.04 上安装 PHP 版本 安装多个 PHP 版本的最简单方法是使用来自 Debian 开发人员 Ondřej Sur 的 PPA。要添加此 PPA,请在终端中运行以下命令。如果要从 PPA 安装软件,则需要 software-properties-common 包。它会自动安装在 Ubuntu 桌面上,但可能会在您的 Ubuntu…...
PHP项目如何自动化测试
开发和测试 测试和开发具有同等重要的作用 从一开始,测试和开发就是相向而行的。测试是开发团队的一支独立的、重要的支柱力量。 测试要具备独立性 独立分析业务需求,独立配置测试环境,独立编写测试脚本,独立开发测试工具。没有…...
WEB 3D技术 three.js 3D贺卡(1) 搭建基本项目环境
好 今天 我也是在网上学的 带着大家一起来做个3D贺卡 首先 我们要创建一个vue3的项目、 先创建一个文件夹 装我们的项目 终端执行 vue create 项目名称 例如 我的名字想叫 greetingCards 就是 vue create greetingcards因为这个名录 里面是全部都小写的 然后 下面选择 vue3 …...
短视频IP运营流程架构SOP模板PPT
【干货资料持续更新,以防走丢】 短视频IP运营流程架构SOP模板PPT 部分资料预览 资料部分是网络整理,仅供学习参考。 抖音运营资料合集(完整资料包含以下内容) 目录 抖音15秒短视频剧本创作公式 在抖音这个短视频平台上&#…...
python爬虫之线程与多进程知识点记录
一、线程 1、概念 线程 在一个进程的内部,要同时干多件事,就需要同时运行多个“子任务”,我们把进程内的这些“子任务”叫做线程 是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。一条线程指…...
基于Java (spring-boot)的停车场管理系统
一、项目介绍 基于Java (spring-boot)的停车场管理系统、预订车位系统、停车缴费系统功能: 登录、注册、后台首页、用户信息管理、车辆信息管理、新增车辆、车位费用设置、停泊车辆查询、车辆进出管理、登录日志查询、个人中心、预定停车位、缴费信息。 适用人群&…...
微软Office 2019 批量授权版
软件介绍 微软办公软件套件Microsoft Office 2019 专业增强版2024年1月批量许可版更新推送!Office2019正式版2018年10月份推出,主要为多人跨平台办公与团队协作打造。Office2019整合对过去三年在Office365里所有功能,包括对Word、Excel、Pow…...
ChatGLM2-6B 大语言模型本地搭建
ChatGLM模型介绍: ChatGLM2-6B 是清华 NLP 团队于不久前发布的中英双语对话模型,它具备了强大的问答和对话功能。拥有最大32K上下文,并且在授权后可免费商用! ChatGLM2-6B的6B代表了训练参数量为60亿,同时运用了模型…...
WindowsServer安装mysql最新版
安装 下载相应mysql安装包: MySQL :: Download MySQL Installer 选择不登陆下载 双击运行下载好的mysql-installer-community-*.*.*.msi 进入类型选择页面,本人需要mysql云服务就选择了server only server only(服务器)&#x…...
gin切片表单验证
在Gin中对切片进行表单验证的步骤与对其他类型的字段进行验证类似。以下是一些基本步骤,我们可以根据具体的需求进行调整: 定义结构体: 创建一个结构体,用于存储表单数据。确保结构体中的字段类型与你预期的表单数据类型一致。 使…...
openssl3.2 - 官方demo学习 - certs
文章目录 openssl3.2 - 官方demo学习 - certs概述笔记官方的实验流程mkcerts.sh - 整理ocsprun.sh - 整理ocspquery.sh - 整理从mkcerts.sh整理出来的27个.bata1_create_certificate_directly.cmda2_Intermediate_CA_request_first.cmda3_Sign_request_CA_extensions.cmda4_Ser…...
Datawhale 大模型基础理论 Day1 引言
开源链接如下:https://github.com/datawhalechina/so-large-lm/blob/main/docs/content/ch01.md 语言模型的概念:即能够赋予每个有意义的词(token)以一定的概率的一个函数的集合。 语言模型可以被用来评估输入的质量,…...
HarmonyOS应用开发学习笔记 UIAbility组件与UI的数据同步 EventHub、globalThis
1、 HarmoryOS Ability页面的生命周期 2、 Component自定义组件 3、HarmonyOS 应用开发学习笔记 ets组件生命周期 4、HarmonyOS 应用开发学习笔记 ets组件样式定义 Styles装饰器:定义组件重用样式 Extend装饰器:定义扩展组件样式 5、HarmonyOS 应用开发…...
leetcode每日一题44
130. 被围绕的区域 图论 dfs/bfs dfs代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本节点所连接的其他节点) {处理节点;dfs(图,选择的节点); // 递归回溯,撤销处理结果} }思路:本题要求找到被x围绕的陆…...
idea写sql语句快捷键提醒,mapper注解开发,mybatis
第一步:注入SQL语言 1.显示上下文操作(没有这个选项的话就选中sql然后直接alt回车快捷键)2.注入语言或引用 3.mysql 第二步:配置MySQL数据库连接 1.首先点击侧边的数据库,再点击上面的加号 2.点击数据源ÿ…...
002 Golang-channel-practice
第二题: 创建一个生产器和接收器,再建立一个无缓冲的channel。生产器负责把数据放进管道里,接收器负责把管道里面的数据打印出来。这里我们开5个协程把数据打印出来。 直接上代码! package mainimport ("fmt" )func …...
MFC为对话框资源添加类
VC6新建一个对话框类型的工程; 建立之后资源中默认有2个对话框,一个是主对话框,About这个是默认建立的关于版权信息的; 然后主对话框有对应的.h和.cpp文件;可以在其中进行编程; 默认建立的有一个 关于 对话框; 在资源中新插入一个对话框,IDD_DIALOG1是对话框ID; 新加…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...
算法刷题-回溯
今天给大家分享的还是一道关于dfs回溯的问题,对于这类问题大家还是要多刷和总结,总体难度还是偏大。 对于回溯问题有几个关键点: 1.首先对于这类回溯可以节点可以随机选择的问题,要做mian函数中循环调用dfs(i&#x…...
