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

数据结构与算法---单调栈结构

数据结构与算法---单调栈结构

  • 1 滑动窗口问题
  • 1 滑动窗口问题


 

1 滑动窗口问题

 

由一个代表题目,引出一种结构

【题目】

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。
例如,数组为[4,3,5,4,3,3,6,7],窗口大小为3时:
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4[3 5 4]3 3 6 7 窗口中最大值为5
4 3[5 4 3] 3 6 7 窗口中最大值为5
4 3 5[4 3 3] 6 7 窗口中最大值为4
4 3 5 4[3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n,窗口大小为w,则一共产生 n-w+1 个窗口的最大值。

请实现一个函数。 输入: 整型数组arr,窗口大小为w

输出:一个长度为 n - w + 1的数组resres[i] 表示每一种窗口状态下的最大值 以本题为例,结果应该
返回{5,5,5,4,6,7}

public class SlidingWindowMaxArrTest {public static void main(String[] args) {int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};final int w = 3;int[] windowMaxArr = getWindowMaxArr(arr, w);for (int i = 0; i < windowMaxArr.length;i++){System.out.print(windowMaxArr[i] + " ");}System.out.println();}/*** @param arr* @param w   窗口的宽度* @return*/public static int[] getWindowMaxArr(int[] arr, int w) {if (arr == null || arr.length < w || w < 1) {return null;}/*** 双端队列 存放数组的索引*  队列的头部存放最大值的索引*/LinkedList<Integer> qMax = new LinkedList<>();// 滑动窗口最大值数组int[] retArr = new int[arr.length - w + 1];int index = 0;for (int i = 0; i < arr.length; i++) {// 放入队列的元素 要保证队列头部的值是最大的// 放入的时候发现队列的最后一个元素没有大于arr[i] 则 弹出while (!qMax.isEmpty() && arr[i] >= arr[qMax.peekLast()]) {qMax.pollLast();}qMax.addLast(i);// 队列中的头部的元素过期if (qMax.peekFirst() == i - w) {qMax.pollFirst();}if (i >= w - 1) {retArr[index++] = arr[qMax.peekFirst()];}}return retArr;}
}

 

1 滑动窗口问题

 

相关文章:

数据结构与算法---单调栈结构

数据结构与算法---单调栈结构 1 滑动窗口问题 1 滑动窗口问题 1 滑动窗口问题 由一个代表题目&#xff0c;引出一种结构 【题目】 有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边&#xff0c;窗口每次向右边滑一个位置。 例如&#xff0c;数组为[4,3,…...

Python爬虫:某书平台的Authorization参数js逆向

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...

Android MediaCodec 框架 基于codec2

系列文章的目的是什么&#xff1f; 粗略&#xff1a; 解码需要哪些基础的服务&#xff1f;标准解码的调用流程&#xff1f;各个流程的作用是什么&#xff1f;解码框架的层次&#xff1f;各个层次的作用&#xff1f; 细化&#xff1a; 解码参数的配置&#xff1f;解码输入数…...

【RocketMQ 系列三】RocketMQ集群搭建(2m-2s-sync)

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精…...

Go TLS服务端绑定证书的几种方式

随着互联网的发展&#xff0c;网站提供的服务类型和规模不断扩大&#xff0c;同时也对Web服务的安全性提出了更高的要求。TLS(Transport Layer Security)[1]已然成为Web服务最重要的安全基础设施之一。默认情况下&#xff0c;一个TLS服务器通常只绑定一个证书[2]&#xff0c;但…...

【算法与数据结构】--高级算法和数据结构--排序和搜索

一、常见排序算法 以下是一些常见的排序算法&#xff0c;包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法的讲解以及附带C#和Java示例&#xff1a; 1.1 冒泡排序 (Bubble Sort) 讲解&#xff1a; 冒泡排序是一种简单的比较排序算法。它多次遍历待排序的…...

【Java】jvm 元空间、常量池(了解)

JDK1.8 以前的 HotSpot JVM 有方法区&#xff0c;也叫永久代&#xff08;permanent generation&#xff09;方法区用于存放已被虚拟机加载的类信息&#xff0c;常量、静态遍历&#xff0c;即编译器编译后的代码JDK1.7 开始了方法区的部分移除&#xff1a;符号引用&#xff08;S…...

Spring Boot自动加载

问&#xff1a;自动装配如何实现的&#xff1f; 答&#xff1a;简单来说就是自动去把第三方组件的Bean装载到IOC容器中&#xff0c;不需要开发人员再去写Bean相关的配置&#xff0c;在springboot应用里面只需要在启动类上去加上SpringBootApplication注解&#xff0c;就可以去实…...

MPNN 模型:GNN 传递规则的实现

首先&#xff0c;假如我们定义一个极简的传递规则 A是邻接矩阵&#xff0c;X是特征矩阵&#xff0c; 其物理意义就是 通过矩阵乘法操作&#xff0c;批量把图中的相邻节点汇聚到当前节点。 但是由于A的对角线都是 0.因此自身的节点特征会被过滤掉。 图神经网络的核心是 吸周围…...

Flink kafka 数据汇不指定分区器导致的问题

背景 在flink中&#xff0c;我们经常使用kafka作为flink的数据汇&#xff0c;也就是目标数据的存储地&#xff0c;然而当我们使用FlinkKafkaProducer作为数据汇连接器时&#xff0c;我们需要注意一些注意事项&#xff0c;本文就来记录一下 使用kafka数据汇连接器 首先我们看…...

【软考】14.1 面向对象基本概念/分析设计测试

《面向对象开发》 对象 现实生活中实际存在的一个实体&#xff1b;构成系统的一个基本单位由对象名、属性和方法组成 类 实体的形式化描述&#xff1b;对象是类的实例&#xff0c;类是对象的模板可分为&#xff1a;实体类&#xff1a;现实世界中真实的实体接口类&#xff08;边…...

MFC-对话框

目录 1、模态和非模态对话框&#xff1a; &#xff08;1&#xff09;、对话框的创建 &#xff08;2&#xff09;、更改默认的对话框名称 &#xff08;3&#xff09;、创建模态对话框 1&#xff09;、创建按钮跳转的界面 2&#xff09;、在跳转的窗口添加类 3&#xff0…...

Essential Steps in Natural Language Processing (NLP)

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

Flink中KeyBy、分区、分组的正确理解

1.Flink中的KeyBy 在Flink中&#xff0c;KeyBy作为我们常用的一个聚合类型算子&#xff0c;它可以按照相同的Key对数据进行重新分区&#xff0c;分区之后分配到对应的子任务当中去。 源码解析 keyBy 得到的结果将不再是 DataStream&#xff0c;而是会将 DataStream 转换为 Key…...

QT6集成CEF3--01 准备工作

QT6集成CEF3--01 准备工作 一、所有使用到的工具软件清单:二、准备工作三、cefclient示例程序四、特别注意 一、所有使用到的工具软件清单: CEF 二进制发行包 cef_binary_117.2.5gda4c36achromium-117.0.5938.152_windows64.tar.bz2 CMake 编译工具 cmake-3.22.6-windows-x86_…...

随机误差理论与测量

文章目录 第1节 随机误差的性质和特点第2节 随机误差的数字特性标准差的估计 第3节 单次测量结果的精度指标第4节 多次测量结果的精度指标算数平均值的分布特性与标准差算数平均值的置信度算数平均值的精度指标&#xff08;常用的有4个) 第5节 非等精度测量 第1节 随机误差的性…...

树莓派4b配置通过smbus2使用LCD灯

出现报错&#xff1a; FileNotFoundError: [Errno 2] No such file or directory: ‘/dev/i2c-1’ 则说明没有打开I2C&#xff0c;可通过如下步骤进行设置 1、打开树莓派配置 sudo raspi-config2、进入Interface Options&#xff0c;配置I2C允许 目前很多python3版本已经不…...

UPS 原理和故障案例分享

摘要:不间断电源UPS (Uninterruptible Power System)&#xff0c;主要是由整流器、 逆变器、静态旁路和储能装置等组成;具备高可靠性、高可用性和高质量的独立 电源。通过对收集的 UPS 故障案例进行分析&#xff0c;从施工&#xff0c;调试和运行三个方面筛选 出四个故障案例与…...

Stream流中的 max()和 sorted()方法

需求&#xff1a;某个公司的开发部门&#xff0c;分为开发 一部 和 二部 &#xff0c;现在需要进行年中数据结算。分析&#xff1a; 员工信息至少包含了&#xff08;名称、性别、工资、奖金、处罚记录&#xff09;开发一部有 4 个员工、开发二部有 5 名员工分别筛选出 2 个部门…...

云上攻防-云原生篇Docker安全权限环境检测容器逃逸特权模式危险挂载

文章目录 前言1、Docker是干嘛的&#xff1f;2、Docker对于渗透测试影响&#xff1f;3、Docker渗透测试点有那些&#xff1f;4、前渗透-判断在Docker中方式一&#xff1a;查询cgroup信息方式二&#xff1a;检查/.dockerenv文件方式三&#xff1a;检查mount信息方式四&#xff1…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...