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

力扣:单调栈算法思路题

单调栈分为单调递增栈和单调递减栈,通过使用单调栈我们可以访问到最近一个比它大(小)的元素。

🍊 单调递增栈:单调递增栈就是从栈底到栈顶数据是依次递增,通常是寻找某方向第一个比它小的元素。
🍊 单调递减栈:单调递减栈就是从栈底到栈顶数据是依次递减,通常是寻找某方向第一个比它大的元素。

适用场景
🍋什么情况适合用单调栈来解决实际问题呢?
🍒 通常是在数组中需要通过比较前后元素的大小关系来找最近的比它大(小)的元素问题时,可以使用单调栈进行求解。

场景示例
1:寻找左边第一个小于它的数

/*** 寻找左边第一个小于它的数* 单调递增栈:单调递增栈就是从栈底到栈顶数据是依次递增,通常是寻找某方向第一个比它小的元素* 单调递减栈:单调递减栈就是从栈底到栈顶数据是依次递减,通常是寻找某方向第一个比它大的元素** 题目描述: 给定一个长度为 n ≤ 10 ^5 的数组 a,输出每个数左边第一个比它小的数,如果不存在则输出 − 1。** 在指针 i 从左往右遍历的过程中,我们可以用一个栈来保存 i 左边的所有元素(不包括i指向的元素)* ,下标越大的元素越接近栈顶,下标越小的元素越接近栈底。* 每次我们访问栈顶,只要栈顶元素大于等于 a [ i ],我们就将栈顶元素弹出,直至栈顶元素小于 a [ i ] ,* 此时输出栈顶元素并将 a [ i ] 压入栈中。 由于栈中保存了 i 左边的所有元素,所以只要有答案,则答案一定在栈中。* 由于每个元素一定会被压入一次且至多弹出一次,因此操作次数至多是2n,故总时间复杂度为O(n)* @param array* @return*/public static int[] findFirstLeftLower(int[] array){Deque<Integer> linkList = new LinkedList<>();int[] ans = new int[array.length];for (int i = 0; i < array.length; i++) {// 如果栈不为空且当前数小于等于栈顶元素,则将栈顶出栈,并通过linkList.push(array[i])将当前元素入栈while(!linkList.isEmpty() && array[i] <= linkList.peek()){// 如果是求右边第一个大于它的数,只需要替换成  array[i] >= linkList.peek()linkList.poll();}if(!linkList.isEmpty()){// 由于栈顶元素存放第一个比当前元素小的数,则取出并给结果数组赋值ans[i] = linkList.peek();}else{ans[i] = -1;}linkList.push(array[i]);}/* for (int i = 0; i < ans.length; i++) {System.out.print(ans[i]+" ");}*/return ans;}

2:寻找左边第一个小于它的数的下标

 /*** 寻找左边第一个小于它的数的下标* 单调递增栈:单调递增栈就是从栈底到栈顶数据是依次递增,通常是寻找某方向第一个比它小的元素* 单调递减栈:单调递减栈就是从栈底到栈顶数据是依次递减,通常是寻找某方向第一个比它大的元素** 题目描述: 给定一个长度为 n ≤ 10 ^5 的数组 a,输出每个数左边第一个比它小的数的下标,如果不存在则输出 − 1。* 我们只需要注意几个点,在当前条件下,咱们栈中存的是下标,而不是值,* 所以需要修改两个地方:* a[linkList.peek()] 而不是linkList.peek(),* 不再是a[i],而是存储对应的下标i* @param array* @return*/public static int[] findFirstLeftLowerPosition(int[] array){Deque<Integer> linkList = new LinkedList<>();int[] ans = new int[array.length];for (int i = 0; i < array.length; i++) {// 如果栈不为空且当前数小于等于栈顶元素,则将栈顶出栈,并通过linkList.push(array[i])将当前元素入栈while(!linkList.isEmpty() && array[i] <= array[linkList.peek()]){// 如果是求右边第一个大于它的数的下标,只需要替换成  array[i] >= linkList.peek()linkList.poll();}if(!linkList.isEmpty()){// 由于栈顶元素存放第一个比当前元素小的数 对应下标,则取出并给结果数组赋值ans[i] = linkList.peek();}else{ans[i] = -1;}linkList.push(i);}/*for (int i = 0; i < ans.length; i++) {System.out.print(ans[i]+" ");}*/return ans;}

3:LeetCode 42. 接雨水

 /*** LeetCode 42. 接雨水* 给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排序的柱子,下雨后能接多少雨水。* @param height* @return*/public static int trapWater(int[] height) {Deque<Integer> linkList = new LinkedList<>();// 总雨水量int ans = 0;int n = height.length;for (int i = 0; i <n ; i++) {// 当前柱子作为右柱子,栈顶元素作为中间柱,中间柱子前面作为左柱,只能接左右两柱最低柱子高度的水while(!linkList.isEmpty() && height[linkList.peek()] <= height[i]){// 右柱比栈顶更高,才能接水。否则的话,就是满足单调递减栈的,那么我们继续入栈。int top = linkList.pop();// 拿出前一个柱子if(linkList.isEmpty()){// 如果这根柱子后,前面没有元素,那就接不了雨水了,因为接雨水的话,至少需要左右两边都有柱子才行。break;}// 记录一下拿到的这根柱子的左边那根柱子的高度int left = linkList.peek();// 根据柱状图推算宽度int currWidth = i-left-1;int currHeight = Math.min(height[left],height[i]) - height[top];ans += currHeight*currWidth;}linkList.push(i);//经过上面一顿操作之后,咱们的栈又满足单调性了,于是将当前元素的下标入栈。}return ans;}

参考资料
单调栈图文详解

相关文章:

力扣:单调栈算法思路题

单调栈分为单调递增栈和单调递减栈&#xff0c;通过使用单调栈我们可以访问到最近一个比它大&#xff08;小&#xff09;的元素。 &#x1f34a; 单调递增栈&#xff1a;单调递增栈就是从栈底到栈顶数据是依次递增&#xff0c;通常是寻找某方向第一个比它小的元素。 &#x1f…...

11 月 25 日 ROS 学习笔记——3D 建模与仿真

文章目录 前言一、在 ROS 中自定义机器人的3D模型1. 在 rviz 里查看3D模型2. xacro 二、Gazebo1. urdf 集成 gazebo2. 综合应用1). 运动控制及里程计2). 雷达仿真3). 摄像头信息仿真4). kinect 深度相机仿真5). 点云 前言 本文为11 月 25 日 ROS 学习笔记——3D 建模与仿真&am…...

MidJourney笔记(3)-Prompts

MidJourney的Prompts介绍 MidJourney的Prompts是MidJourney的核心之一,这也是我们后续使用MidJourney过程中最重要的工作内容,根据生成的图片,不断的优化我们的Prompts内容。 那Prompts的中文意思是提示的意思。 Prompts的提示语有很多,最基础的用法就是: /imagine prompt…...

贪心 D. Least Cost Bracket Sequence

Problem - D - Codeforces 题目大意&#xff1a;给一个只包含(&#xff0c;)&#xff0c;?三个字符的字符串。每个?可以转为(或者)&#xff0c;对于第 i i i个?转为(需要花费 a i a_i ai​&#xff0c;转为)需要花费 b i b_i bi​。现在问能否让该字符串转为合法的括号匹配…...

iOS APP包分析工具 | 京东云技术团队

介绍 分享一款用于分析iOSipa包的脚本工具&#xff0c;使用此工具可以自动扫描发现可修复的包体积问题&#xff0c;同时可以生成包体积数据用于查看。这块工具我们团队内部已经使用很长一段时间&#xff0c;希望可以帮助到更多的开发同学更加效率的优化包体积问题。 工具下载…...

在 VSCode 中使用 GDB 进行 C/C++ 程序调试(图文版)

(꒪ꇴ꒪ )&#xff0c;Hello我是祐言QAQ我的博客主页&#xff1a;C/C语言&#xff0c;数据结构&#xff0c;Linux基础&#xff0c;ARM开发板&#xff0c;网络编程等领域UP&#x1f30d;快上&#x1f698;&#xff0c;一起学习&#xff0c;让我们成为一个强大的攻城狮&#xff0…...

任意文件读取漏洞理解

任意文件读取漏洞理解 1. 漏洞描述&#xff1a; 任意文件读取漏洞是指攻击者可以利用漏洞读取系统上的任意文件&#xff0c;包括敏感信息的配置文件、用户数据甚至系统文件&#xff0c;从而获取未经授权的访问权限。 2. 漏洞原理&#xff1a; 这种漏洞通常是由程序处理用户输入…...

linux 安装yum

问题1&#xff1a;File "/usr/libexec/urlgrabber-ext-down", line 28 except OSError, e: ^ 问题2&#xff1a;yum File "/usr/bin/yum", line 30 except KeyboardInterrupt, e: ^ vim /usr/…...

数学启发式

学习资料&#xff1a; 优化求解器 | Gurobi 数学启发式算法&#xff1a;参数类型与案例实现 数学启发式算法 | 可行性泵 (Feasibility Pump)算法精讲&#xff1a;一份让您满意的【理论介绍编程实现数值实验】学习笔记(PythonGurobi实现) 大佬到底是大佬&#xff01;这些资料太…...

Win10/Win11 使用Wsl的Ubuntu 子系统搭建CGO环境,相当于Ubuntu下开发。GO环境CGO搭建,支持交叉编译

背景&#xff1a; 之前是使用Mac 开发&#xff0c;最近切换到win11下面。发现使用cgo编译有问题。 下面记载了我的使用方法。 环境&#xff1a; win11&#xff08;win10理论一样&#xff09; win11 安装了wsl2的环境&#xff0c;并且安装了ubuntu系统。 在win11 上面安装了g…...

CSS新特性(2-2)

CSS新特性&#xff08;2-2&#xff09; 前言box相关box-shadow background背景rgba颜色与透明度transform:rotate(Xdeg) 2D旋转transform:tranlate 平移 前言 本文继续讲解CSS3其他的新特性&#xff0c;想看之前新特性点击这里&#xff0c;那么好本文正式开始。 box相关 box…...

为什么,word文件在只读模式下,仍然能编辑?

Word文档设置了只读模式&#xff0c;是可以编辑的&#xff0c;但是当我们进行保存的时候就会发现&#xff0c;word提示需要重命名并选择新路径才能够保存。 这种操作&#xff0c;即使可以编辑文字&#xff0c;但是原文件是不会受到影响的&#xff0c;编辑之后的word文件会保存到…...

29 - 装饰器模式:如何优化电商系统中复杂的商品价格策略?

开始今天的学习之前&#xff0c;我想先请你思考一个问题。假设现在有这样一个需求&#xff0c;让你设计一个装修功能&#xff0c;用户可以动态选择不同的装修功能来装饰自己的房子。例如&#xff0c;水电装修、天花板以及粉刷墙等属于基本功能&#xff0c;而设计窗帘装饰窗户、…...

逆矩阵相关性质与例题

1.方阵的行列式&#xff1a;就是将方阵中的每一个元素转换至行列式中。 1.性质一&#xff1a;转置方阵的行列式等于转置前的行列式。&#xff08;对标性质&#xff1a;行列式与它的转置行列式相等&#xff09; 2.性质二&#xff1a;|ka||a|*k的n次方&#xff0c;n为方阵阶数。 …...

Ruoyi项目传List到后台并使用Excel模板下载数据的方法以及遇到的各种前后端数据交互问题

import { download } from @/utils/requestconst app = createApp(App)// 全局方法挂载 app.config.globalProperties.download = download 首先因为ruoyi-ui中的main.js有配置如上全局注册: 因此只需要在vue中定义一个方法直接使用this.download调用下载即可: (download的3…...

区块链技术将如何影响未来的数字营销?

你是否听腻了区块链和数字营销等流行语&#xff0c;却不明白它们对未来意味着什么&#xff1f;那么&#xff0c;准备好系好安全带吧&#xff0c;因为区块链技术将彻底改变我们对数字营销的看法。从建立消费者信任到提高透明度和效率&#xff0c;其可能性是无限的。 让我们来探…...

小程序wx:if和hidden的区别?

wx:if&#xff1a;wx:if 是一个完整的条件渲染指令&#xff0c;当它的表达式为真时&#xff0c;才会渲染该指令所在的元素。如果表达式的值为假&#xff0c;则不会渲染该元素。这意味着在表达式为假时&#xff0c;该元素及其子元素都不会被渲染&#xff0c;就像它们从未存在过一…...

分布式幂等

分布式幂等 在分布式系统、网络通信和数据库操作中&#xff0c;幂等性是一个非常重要的概念&#xff0c;特别是在面对可能发生网络故障、消息重复、或者系统崩溃等情况时。 举个简单的例子&#xff0c;考虑一个银行转账的操作。如果转账操作是幂等的&#xff0c;那么无论你执…...

大数据 DataX-Web 详细安装教程

目录 一、DataX-Web 介绍 1.1 DataX-Web 是什么 1.2 DataX-Web 架构 二、DataX-Web 安装部署 2.1 环境要求 2.2 安装 2.3 部署 2.4 数据库初始化 2.5 配置 2.6 启动服务 2.6.1 一键启动所有服务 2.6.2 一键取消所有服务 2.7 查看服务&#xff08;注意&#xff01…...

CSS3媒体查询实现不同宽度的下不同内容的展示

文章目录 前言CSS3 多媒体查询实例520 到 699px 宽度 - 添加邮箱图标700 到 1000px - 添加文本前缀信息大于 1001px 宽度 - 添加邮件地址大于 1151px 宽度 - 添加图标代码后言 前言 hello world欢迎来到前端的新世界 &#x1f61c;当前文章系列专栏&#xff1a;CSS &#x1f43…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...