代码随想录算法训练营DAY13 | 栈与队列 (3)

news/2024/2/24 8:38:57/文章来源:https://blog.csdn.net/weixin_51560545/article/details/136048846

一、LeetCode 239 滑动窗口最大值

题目链接:239.滑动窗口最大值icon-default.png?t=N7T8https://leetcode.cn/problems/sliding-window-maximum/

思路:使用单调队列,只保存窗口中可能存在的最大值,从而降低时间复杂度。

public class MyQueue{Deque<Integer> queue = new LinkedList<>();//弹出元素时,判断要窗口弹出的数值是否等于队列出口的数值void poll(int val){if(!queue.isEmpty() && val == queue.peek()){queue.poll();}}//添加元素时,判断要添加的元素是否大于队列入口处的元素//如果大于,就将入口处元素弹出,保证队列单调递减void offer(int val){while(!queue.isEmpty() && val > queue.getLast()){queue.removeLast();}queue.offer(val);}//栈顶始终为最大值int peek(){return queue.peek();}
}
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length == 1){return nums;}int len = nums.length - k + 1;int[] ans = new int[len];int index = 0;MyQueue queue = new MyQueue();//先把前k个元素入队for(int i = 0; i < k; i++){queue.offer(nums[i]);}//记录前k个元素中的最大值ans[index++] = queue.peek();for(int i = k; i < nums.length; i++){//弹出 + 入队queue.poll(nums[i-k]);queue.offer(nums[i]);//记录每组窗口的最大值ans[index++] = queue.peek();}return ans;}
}

 二、LeetCode 347 前k个高频元素

题目链接:347.前k个高频元素icon-default.png?t=N7T8https://leetcode.cn/problems/top-k-frequent-elements/

思路:维护大小为k的小顶堆,遍历map<元素,出现次数>每次弹出出现次数最少的元素,最终得到出现次数前k的元素。

class Solution {public int[] topKFrequent(int[] nums, int k) {//基于小顶堆实现Map<Integer,Integer> map = new HashMap<>();for(int a : nums){map.put(a,map.getOrDefault(a,0) + 1);}//在优先队列里存储二元组 出现次数低的在队头PriorityQueue<int[]> pq = new PriorityQueue<>((p1,p2) -> p1[1]-p2[1]);//map.Entry是键值对for(Map.Entry<Integer,Integer> entry : map.entrySet()){//pq的元素个数小于k,直接添加if(pq.size() < k){pq.add(new int[]{entry.getKey(),entry.getValue()});}else{//当前元素出现次数大于pq队头(小顶堆堆顶)元素if(entry.getValue() > pq.peek()[1]){pq.poll();pq.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] ans = new int[k];for(int i = 0; i < k; i++){ans[i] = pq.poll()[0];}return ans;}
}

补充:重写comparTo()方法 -- (a1,a2)->(a1-a2)为按递增顺序排列

参考文章:Java 优先级队列-CSDN博客

三、今日小结

        最近好疲劳啊,今天补了昨天的遗漏,吃个饭饭开启下一篇 ^*^

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_963372.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】11 堆栈(顺序存储和链式存储)

定义 可认为是具有一定约束的线性表&#xff0c;插入和删除操作都在一个称为栈顶的端点位置。也叫后入先出表&#xff08;LIFO&#xff09; 类型名称&#xff1a;堆栈&#xff08;STACK&#xff09; 数据对象集&#xff1a; 一个有0个或者多个元素的有穷线性表。 操作集&#…

探索现代Web前端开发框架:选择最适合你的工具

在当今快速发展的Web开发领域&#xff0c;前端开发框架的选择显得尤为关键。这些框架可以帮助我们更高效地构建出交互性强、性能卓越的用户界面。本文将带你了解几个当前最受欢迎的Web前端开发框架&#xff0c;并帮助你根据自己的需求选择最合适的工具。 1. React React由Fac…

sheng的学习笔记-网络爬虫scrapy框架

基础知识&#xff1a; scrapy介绍 何为框架&#xff0c;就相当于一个封装了很多功能的结构体&#xff0c;它帮我们把主要的结构给搭建好了&#xff0c;我们只需往骨架里添加内容就行。scrapy框架是一个为了爬取网站数据&#xff0c;提取数据的框架&#xff0c;我们熟知爬虫总…

新年福利:《YOLO目标检测》送书活动

博主简介 AI小怪兽&#xff0c;YOLO骨灰级玩家&#xff0c;1&#xff09;YOLOv5、v7、v8优化创新&#xff0c;轻松涨点和模型轻量化&#xff1b;2&#xff09;目标检测、语义分割、OCR、分类等技术孵化&#xff0c;赋能智能制造&#xff0c;工业项目落地经验丰富&#xff1b; …

docker 基于容器创建本地web容器化镜像

一、docker 基于容器创建本地web容器化镜像 1、启动指定buysbox 镜像 docker run --name b1 -it busybox:latest 2、创建目录&#xff0c;并创建html mkdir -p /data/html vi index.html 内容自定义例如&#xff1a;<h1>welcome to busybox<h1> 3、新增窗口&am…

【JVM篇】ThreadLocal中为什么要使用弱引用

文章目录 &#x1f354;ThreadLocal中为什么要使用弱引用⭐总结 &#x1f354;ThreadLocal中为什么要使用弱引用 ThreadLocal可以在线程中存放线程的本地变量&#xff0c;保证数据的线程安全 ThreadLocal是这样子保存对象的&#xff1a; 在每个线程中&#xff0c;存放了一个…

3D高斯溅射:面向三维场景的实时渲染技术

1. 前言 高斯溅射技术【1】一经推出&#xff0c;立刻引起学术界和工业界的广泛关注。相比传统的隐式神经散射场渲染技术&#xff0c;高斯溅射依托椭球空间&#xff0c;显性地表示多目图像的三维空间关系&#xff0c;其计算效率和综合性能均有较大的提升&#xff0c;且更容易理…

Java+SpringBoot:高校竞赛管理新篇章

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

使用client-only 解决组件不兼容SSR问题

目录 前言 一、解决方案 1.基于Nuxt 框架的SSR应用 2.基于vue2框架的应用 3.基于vue3框架的应用 二、总结 往期回顾 前言 最近在我的单页面SSR应用上开发JSON编辑器功能&#xff0c;在引入组件后直接客户端跳转OK&#xff0c;但是在直接加载服务端渲染的时候一直报这…

【flink状态管理(三)】StateBackend的整体设计、StateBackend创建说明

文章目录 一. 状态后端概述二. StateBackend的整体设计1. 核心功能2. StateBackend的UML3. 小结 三. StateBackend的加载与初始化1. StateBackend创建概述2. StateBackend创建过程 一. 状态后端概述 StateBackend作为状态存储后端&#xff0c;提供了创建和获取KeyedStateBacke…

postgresql 手动清理wal日志的101个坑

新年的第一天&#xff0c;总结下去年遇到的关于WAL日志清理的101个坑&#xff0c;以及如何相对安全地进行清理。前面是关于WAL日志堆积的原因分析&#xff0c;清理相关可以直接看第三部分。 首先说明&#xff0c;手动清理wal日志是一个高风险的操作&#xff0c;尤其对于带主从的…

前端vite+vue3——自动化配置路由布局

文章目录 ⭐前言&#x1f496;vue3系列文章 ⭐ 自动化配置路由&#x1f496;引入vite版本自定义目录映射&#x1f496;自动化读取文件下的路由&#x1f496;main入口加载路由&#x1f496;入口app.vue配置&#x1f496;layout基础布局配置&#x1f496;效果 ⭐总结⭐结束 ⭐前言…

搜索二维矩阵[中等]

一、题目 给你一个满足下述两条属性的m x n整数矩阵&#xff1a; 【1】每行中的整数从左到右按非严格递增顺序排列。 【2】每行的第一个整数大于前一行的最后一个整数。 给你一个整数target&#xff0c;如果target在矩阵中&#xff0c;返回true&#xff1b;否则&#xff0c;返…

【Linux技术宝典】Linux入门:揭开Linux的神秘面纱

文章目录 官网Linux 环境的搭建方式一、什么是Linux&#xff1f;二、Linux的起源与发展三、Linux的核心组件四、Linux企业应用现状五、Linux的发行版本六、为什么选择Linux&#xff1f;七、总结 Linux&#xff0c;一个在全球范围内广泛应用的开源操作系统&#xff0c;近年来越来…

树莓派编程基础与硬件控制

1.编程语言 Python 是一种泛用型的编程语言&#xff0c;可以用于大量场景的程序开发中。根据基于谷歌搜 索指数的 PYPL&#xff08;程序语言流行指数&#xff09;统计&#xff0c;Python 是 2019 年 2 月全球范围内最为流行 的编程语言 相比传统的 C、Java 等编程语言&#x…

生成树技术华为ICT网络赛道

9.生成树 目录 9.生成树 9.1.生成树技术概述 9.2.STP的基本概念及工作原理 9.3.STP的基础配置 9.4.RSTP对STP的改进 9.5.生成树技术进阶 9.1.生成树技术概述 技术背景&#xff1a;二层交换机网络的冗余性与环路 典型问题1&#xff1a;广播风暴 典型问题2&#xff1a;MA…

《UE5_C++多人TPS完整教程》学习笔记10 ——《P11 设置加入游戏会话(Setup for Joining Sessions)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P11 设置加入游戏会话&#xff08;Setup for Joining Sessions&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&…

Linux开发:PAM1 介绍

PAM(Pluggable Authentication Modules )是Linux提供的一种通用的认证方式,他可以根据需要动态的加载认证模块,从而减少认证开发的工作量以及提供认证的灵活度。 1.PAM的框架 PAM的框架由一下几个部分构成 1)应用程序,即需要使用认证服务的程序,这些应用程序是使用抽象…

单例模式 C++

6 种 单例 的手写&#xff0c;都是懒汉&#xff08;饿汉代码在 “懒汉 / 饿汉的区别”&#xff09; 目录 ✊前言 &#x1f33c;GPT解析 &#x1f33c;概念解析 RAII 懒汉 / 饿汉的区别 特点 举例 单例 -- 伪代码 适用场景 单例 -- 实现方式 优缺点 &#x1f382;手…

【Iceberg学习二】Branch和Tag在Iceberg中的应用

Iceberg 表元数据保持一个快照日志&#xff0c;记录了对表所做的更改。快照在 Iceberg 中至关重要&#xff0c;因为它们是读者隔离和时间旅行查询的基础。为了控制元数据大小和存储成本&#xff0c;Iceberg 提供了快照生命周期管理程序&#xff0c;如 expire_snapshots&#xf…