算法体系-26 第二十六节:第26节:单调栈结构 (5节)

一 单调栈知识讲解

1.1描述

一个数组里面想的到每个位置与他最近的左边和右边比他小的最近的信息

1.2 分析
通过单调栈的特点,for遍历数组中的每个数,当前数来的时候对比单调栈中的数进行每个数的左右判断完满足条件的进行更新到当前i种的

int[][] res = new int[arr.length][2]; 里0和1中去

res[j][0] = leftLessIndex;
res[j][1] = i;

1.2.1 无重复值版本

1.2.2 有重复值版本

1.3 代码
无重复值情况

// arr = [ 3, 1, 2, 3]//         0  1  2  3//  [//     0 : [-1,  1]//     1 : [-1, -1]//     2 : [ 1, -1]//     3 : [ 2, -1]//  ]public static int[][] getNearLessNoRepeat(int[] arr) {int[][] res = new int[arr.length][2];// 只存位置!Stack<Integer> stack = new Stack<>();for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数,arr[i]while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {int j = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[j][0] = leftLessIndex;res[j][1] = i;}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[j][0] = leftLessIndex;res[j][1] = -1;}return res;}

有重复值情况

public static int[][] getNearLess(int[] arr) {int[][] res = new int[arr.length][2];Stack<List<Integer>> stack = new Stack<>();for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {List<Integer> popIs = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popIs) {res[popi][0] = leftLessIndex;res[popi][1] = i;}}if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {stack.peek().add(Integer.valueOf(i));} else {ArrayList<Integer> list = new ArrayList<>();list.add(i);stack.push(list);}}while (!stack.isEmpty()) {List<Integer> popIs = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popIs) {res[popi][0] = leftLessIndex;res[popi][1] = -1;}}return res;}

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

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

相关文章

【鸿蒙学习笔记】Stage模型工程目录

官方文档&#xff1a;应用配置文件概述&#xff08;Stage模型&#xff09; 目录标题 FA模型和Stage模型工程级目录模块级目录app.json5module.json5程序执行流程程序基本结构开发调试与发布流程 FA模型和Stage模型 工程级目录 模块级目录 app.json5 官方文档&#xff1a;app.j…

【51单片机入门】数码管原理

文章目录 前言共阴极与共阳极数码管多个数码管显示原理 总结 前言 在我们的日常生活中&#xff0c;数码管被广泛应用于各种电子设备中&#xff0c;如电子表、计时器、电子钟等。数码管的主要功能是显示数字和一些特殊字符。在这篇文章中&#xff0c;我们将探讨数码管的工作原理…

【机器学习】机器学习与自然语言处理的融合应用与性能优化新探索

引言 自然语言处理&#xff08;NLP&#xff09;是计算机科学中的一个重要领域&#xff0c;旨在通过计算机对人类语言进行理解、生成和分析。随着深度学习和大数据技术的发展&#xff0c;机器学习在自然语言处理中的应用越来越广泛&#xff0c;从文本分类、情感分析到机器翻译和…

项目部署_持续集成_Jenkins

1 今日内容介绍 1.1 什么是持续集成 持续集成&#xff08; Continuous integration &#xff0c; 简称 CI &#xff09;指的是&#xff0c;频繁地&#xff08;一天多次&#xff09;将代码集成到主干 持续集成的组成要素 一个自动构建过程&#xff0c; 从检出代码、 编译构建…

【Python】基于KMeans的航空公司客户数据聚类分析

&#x1f490;大家好&#xff01;我是码银~&#xff0c;欢迎关注&#x1f490;&#xff1a; CSDN&#xff1a;码银 公众号&#xff1a;码银学编程 实验目的和要求 会用Python创建Kmeans聚类分析模型使用KMeans模型对航空公司客户价值进行聚类分析会对聚类结果进行分析评价 实…

linux-5.10.110内核源码分析 - Freescale ls1012a pcie host驱动

1、dts pcie设备树 1.1、pcie设备树 pcie1: pcie3400000 {compatible "fsl,ls1012a-pcie";reg <0x00 0x03400000 0x0 0x00100000 /* controller registers */0x40 0x00000000 0x0 0x00002000>; /* configuration space */reg-names "regs", &…

尚硅谷k8s 2

p54-56 k8s核心实战 service服务发现 Service:将一组 Pods 公开为网络服务的抽象方法。 #暴露Deploy,暴露deploy会出现在svc kubectl expose deployment my-dep --port8000 --target-port80#使用标签检索Pod kubectl get pod -l appmy-depapiVersion: v1 kind: Service metad…

Python酷库之旅-第三方库Pandas(006)

目录 一、用法精讲 10、pandas.DataFrame.to_excel函数 10-1、语法 10-2、参数 10-3、功能 10-4、返回值 10-5、说明 10-6、用法 10-6-1、数据准备 10-6-2、代码示例 10-6-3、结果输出 11、pandas.ExcelFile类 11-1、语法 11-2、参数 11-3、功能 11-4、返回值 …

您的私人办公室!-----ONLYOFFICE8.1版本的桌面编辑器测评

随时随地创建并编辑文档&#xff0c;还可就其进行协作 ONLYOFFICE 文档是一款强大的在线编辑器&#xff0c;为您使用的平台提供文本文档、电子表格、演示文稿、表单和 PDF 编辑工具。 网页地址链接&#xff1a; https://www.onlyoffice.com/zh/office-suite.aspxhttps://www…

Zynq系列FPGA实现SDI视频编解码,基于GTX高速接口,提供5套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案在Xilinx--Kintex系列FPGA上的应用 3、详细设计方案设计原理框图SDI 输入设备Gv8601a 均衡器GTX 解串与串化SMPTE SD/HD/3G SDI IP核BT1120转RGB图像缓存视频读取控制HDMI输出RGB转BT1120Gv8500 驱…

Docker 运行Nacos无法访问地址解决方法

参考我的上一篇文章去配置好镜像加速器&#xff0c;镜像加速器不是配置越多越好&#xff0c;重试次数多了会失败 Dockerhub无法拉取镜像配置阿里镜像加速器-CSDN博客 错误的尝试 最开始按照网上的方式去配了一大堆&#xff0c;发现下不下来。 镜像源地址&#xff1a;https:…

Kafka-服务端-副本同步-源码流程

杂 在0.9.0.0之前&#xff0c;Kafka提供了replica lag.max.messages 来控制follower副本最多落后leader副本的消息数量&#xff0c;follower 相对于leader 落后当超过这个数量的时候就判定该follower是失效的&#xff0c;就会踢出ISR&#xff0c;这里的指的是具体的LEO值。 对…

工程文件参考——CubeMX+LL库+SPI主机 阻塞式通用库

文章目录 前言CubeMX配置SPI驱动实现spi_driver.hspi_driver.c 额外的接口补充 前言 SPI&#xff0c;想了很久没想明白其DMA或者IT比较好用的方法&#xff0c;可能之后也会写一个 我个人使用场景大数据流不多&#xff0c;如果是大批量数据交互自然是DMA更好用&#xff0c;但考…

如何摆脱反爬虫机制?

在网站设计时&#xff0c;为了保证服务器的稳定运行&#xff0c;防止非法数据访问&#xff0c;通常会引入反爬虫机制。一般来说&#xff0c;网站的反爬虫机制包括以下几种&#xff1a; 1. CAPTCHA&#xff1a;网站可能会向用户显示CAPTCHA&#xff0c;要求他们在访问网站或执行…

华为实训案例

案例下载 案例内包含空拓扑图、配置完整的拓扑、以及步骤脚本文档&#xff0c;可按需下载。 拓扑图 任务清单 &#xff08;一&#xff09;基础配置 根据附录1拓扑图、附录2地址规划表、附录3设备编号表&#xff0c;配置设备接口及主机名信息。 将所有终端超时时间设置为永不…

【nvm】如何使用nvm优雅的管理Node.js

希望文章能给到你启发和灵感&#xff5e; 如果觉得文章对你有帮助的话&#xff0c;点赞 关注 收藏 支持一下博主吧&#xff5e; 阅读指南 开篇说明一、基础环境说明1.1 硬件环境1.2 软件环境 二、什么是nvm?2.1 概念2.1 安装2.1.1 对于Mac系统2.1.2 对于Windows系统2.1.3 对于…

逻辑这回事(八)---- 时钟与复位

时钟设计总结 时钟和复位是FPGA设计的基础&#xff0c;本章总结了一些逻辑时钟复位设计、使用中出现的问题&#xff0c;给出了设计要点&#xff0c;避免后续问题重犯。时钟和复位&#xff0c;本文都先从板级谈起&#xff0c;再到FPGA芯片级&#xff0c;最后到模块级别。仅在此…

基于单片机的粉尘检测报警防护系统研究

摘要 &#xff1a; 粉尘检测是环境保护的重要环节&#xff0c;传统的粉尘检测防护系统的预防方式较为单一。本文设计了一种基于单片机的粉尘检测报警防护系统&#xff0c;能有效地检测粉尘浓度&#xff0c;进行多种方式的报警防护&#xff0c;以保证工作人员的生命健康和安全。…

软件设计之Java入门视频(11)

软件设计之Java入门视频(11) 视频教程来自B站尚硅谷&#xff1a; 尚硅谷Java入门视频教程&#xff0c;宋红康java基础视频 相关文件资料&#xff08;百度网盘&#xff09; 提取密码&#xff1a;8op3 idea 下载可以关注 软件管家 公众号 学习内容&#xff1a; 该视频共分为1-7…

Floyd判圈算法——环形链表(C++)

Floyd判圈算法(Floyd Cycle Detection Algorithm)&#xff0c;又称龟兔赛跑算法(Tortoise and Hare Algorithm)&#xff0c;是一个可以在有限状态机、迭代函数或者链表上判断是否存在环&#xff0c;求出该环的起点与长度的算法。 …