算法体系-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.mfbz.cn/a/776675.html

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

相关文章

MySQL索引教程(01):创建索引

文章目录 MySQL 创建索引索引介绍MySQL CREATE INDEX 语法MySQL 索引类型MySQL CREATE INDEX 实例结论 MySQL 创建索引 对于一个具有大量数据行的表&#xff0c;如果你根据某个查询条件检索数据时很慢&#xff0c;可能是因为你没有在检索条件相关的列上创建索引。 索引类似于…

平价猫粮新选择!福派斯鲜肉猫粮,让猫咪享受美味大餐!

福派斯鲜肉猫粮&#xff0c;作为一款备受铲屎官们青睐的猫粮品牌&#xff0c;凭借其卓越的品质和高性价比&#xff0c;为众多猫主带来了健康与美味的双重享受。接下来&#xff0c;我们将从多个维度对这款猫粮进行解析&#xff0c;让各位铲屎官更加全面地了解它的魅力所在。 1️…

查看电脑显卡(NVIDIA)应该匹配什么版本的CUDA Toolkit

被串行计算逼到要吐时&#xff0c;决定重拾CUDa了&#xff0c;想想那光速般的处理感觉&#xff08;夸张了&#xff09;不要太爽&#xff0c;记下我的闯关记录。正好我的电脑配了NVIDIA独显&#xff0c;GTX1650&#xff0c;有菜可以炒呀&#xff0c;没有英伟达的要绕道了。回到正…

详细分析SQL语句中的硬解析、软解析、软软解析基本知识

目录 前言1. 基本知识2. Demo 前言 从实战中探索 图为全局搜索且在高并发下&#xff0c;会引发硬解析&#xff0c;导致CPU崩溃 1. 基本知识 解析 (parsing) 是数据库在处理 SQL 语句时必不可少的一步&#xff0c;它将 SQL 语句转换为数据库可以执行的低级指令 硬解析 (Hard…

昇思25天学习打卡营第18天|Pix2Pix实现图像转换

Pix2Pix概述 Pix2Pix是基于条件生成对抗网络实现的一种深度学习图像转换模型。Pix2Pix是将cGAN应用于有监督的图像到图像翻译&#xff0c;包括生成器和判别器。 基础原理 cGAN的生成器是将输入图片作为指导信息&#xff0c;由输入图像不断尝试生成用于迷惑判别器的“假”图像…

c++ 附赠课程的知识点记录

&#xff08;1&#xff09; 静态变量的赋值 再一个例子&#xff1a; &#xff08;2&#xff09; 一般在定义类的赋值运算符函数时&#xff0c; operator ( const A& a ) 函数&#xff0c;应避免自赋值的情况&#xff0c;就是把对象 a 又赋值给 对象a 如同 a a 这样的情况…

类和对象深入理解

目录 static成员概念静态成员变量面试题补充代码1代码2代码3如何访问private中的成员变量 静态成员函数静态成员函数没有this指针 特性 友元友元函数友元类 内部类特性1特性2 匿名对象拷贝对象时的一些编译器优化 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接…

C++ | Leetcode C++题解之第217题存在重复元素

题目&#xff1a; 题解&#xff1a; class Solution { public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> s;for (int x: nums) {if (s.find(x) ! s.end()) {return true;}s.insert(x);}return false;} };

【PB案例学习笔记】-27制作一个控制任务栏显示与隐藏的小程序

写在前面 这是PB案例学习笔记系列文章的第27篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…

视频参考帧和重构帧复用

1、 视频编码中的参考帧和重构帧 从下图的编码框架可以看出&#xff0c;每编码一帧需要先使用当前帧CU(n)减去当前帧的参考帧CU&#xff08;n&#xff09;得到残差。同时&#xff0c;需要将当前帧的重构帧CU*&#xff08;n&#xff09;输出&#xff0c;然后再读取重构帧进行预测…

Pandas数据可视化详解:大案例解析(第27天)

系列文章目录 Pandas数据可视化解决不显示中文和负号问题matplotlib数据可视化seaborn数据可视化pyecharts数据可视化优衣库数据分析案例 文章目录 系列文章目录前言1. Pandas数据可视化1.1 案例解析&#xff1a;代码实现 2. 解决不显示中文和负号问题3. matplotlib数据可视化…

HTTP代理服务器:深度解析与应用

“随着互联网的飞速发展&#xff0c;HTTP代理服务器在网络通信中扮演着越来越重要的角色。它们作为客户端和服务器之间的中介&#xff0c;不仅优化了网络性能&#xff0c;还提供了强大的安全性和隐私保护功能。” 一、HTTP代理服务器的概念与作用 HTTP代理服务器是一种能够接…

Qt扫盲-QRect矩形描述类

QRect矩形描述总结 一、概述二、常用函数1. 移动类2. 属性函数3. 判断4. 比较计算 三、渲染三、坐标 一、概述 QRect类使用整数精度在平面中定义一个矩形。在绘图的时候经常使用&#xff0c;作为一个二维的参数描述类。 一个矩形主要有两个重要属性&#xff0c;一个是坐标&am…

前端面试题16(跨域问题)

跨域问题源于浏览器的同源策略&#xff08;Same-origin policy&#xff09;&#xff0c;这一策略限制了来自不同源的“写”操作&#xff08;比如更新、删除数据等&#xff09;&#xff0c;同时也限制了读操作。当一个网页尝试请求与自身来源不同的资源时&#xff0c;浏览器会阻…

设计模式探索:代理模式

1. 什么是代理模式 定义 代理模式是一种结构型设计模式&#xff0c;通过为其他对象提供一种代理以控制对这个对象的访问。代理对象在客户端和实际对象之间起到中介作用&#xff0c;可以在不改变真实对象的情况下增强或控制对真实对象的访问。 目的 代理模式的主要目的是隐…

着急,为啥AI叫好不叫座啊?

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 李彦宏在2024世界人工智能大会上说&#xff1a; 没有应用&#xff0c;光有基础模型&#xff0c;不管是开源还是闭源都一文不值&#xff0c;所以我从去年下半年开始讲&#xff0c;大家不要卷模型了&#xff0c;要去…

MySQL---事务管理

1.关于事务 理解和学习事务&#xff0c;不能只站在程序猿的角度来理解事务&#xff0c;而是要站在使用者&#xff08;用户&#xff09;的角度来理解事务。 比如支付宝转账&#xff0c;A转了B100块前&#xff0c;在程序猿的角度来看&#xff0c;是两条update操作&#xff0c;A …

PCDN技术如何提高内容分发效率?(贰)

PCDN技术通过以下方式提高内容分发效率: 1.利用用户设备作为分发节点:与传统的 CDN技术主要依赖中心化服务器不同&#xff0c; PCDN技术利用用户的设备作为内容分发的节点。当用户下载内容时&#xff0c;他们的设备也会成为内容分发的一部分&#xff0c;将已下载的内容传递给其…

项目部署_持续集成_Jenkins

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

树状数组实现 查找逆序对

题意&#xff1a; 输入一个整数n。 接下来输入一行n个整数 。 1< < n ,且每个数字只会出现一次 题解&#xff1a; 按每个数字的大小存入树状数组 #include<bits/stdc.h> using namespace std; #define ll long long const int N10000; int arr[N]; ll a[N];…