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

代码随想录 单调栈part2

503. 下一个更大元素 II

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。

思路:在后面多续一段

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:dp = [-1] * len(nums)stack = []for i in range(len(nums)*2):while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):dp[stack[-1]] = nums[i%len(nums)]stack.pop()stack.append(i%len(nums))return dp

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水

思路:

1. 双指针(dp):从列的角度去看,每一列可以装的雨水取决于左边最高的柱子和右边最高的柱子和该列的高度的差。可以使用双指针,当前列的左边最高的柱子可以由前一列的左边最高柱子转移而来,同理列的右边最高的柱子可以由后一列的左边最高柱子转移而来。

class Solution:def trap(self, height: List[int]) -> int:left_dp = [0 for _ in range(len(height))]  # 记录左边最高的柱子right_dp = [0 for _ in range(len(height))]  # 记录右边最高的柱子ans = 0left_max= 0right_max = 0for i in range(1, len(height)):  # 求每一列左边最高的柱子left_dp[i] = max(left_dp[i-1], height[i-1])for j in range(len(height) -2 , 0, -1):  # 求每一列右边最高的柱子right_dp[j] = max(right_dp[j+1], height[j+1])for k in range(len(height)):  # 求可以接住的雨水h = min(left_dp[k], right_dp[k]) - height[k]ans += max(0, h)return ans

2. 单调栈

从行的角度去看,需要找到一个个凹槽,大的凹槽又有小凹槽,可以将凹槽都归一为底部平坦的凹槽,如果有小凹槽,再计算小凹槽的积水量后,就认为其填上了,这样每一个凹槽都是底部平坦的凹槽,凹槽积水量就是 雨水高度 * 雨水深度,其中雨水高度为min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度,雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1。找的是该元素左边和右边第一个大于该元素的位置和高度,可以用单调栈。

单调栈性质,从栈头到栈尾单调递增,当遇到比栈头元素大的就是出现凹槽,计算凹槽的雨水体积。

class Solution:def trap(self, height: List[int]) -> int:stack = [0]result = 0for i in range(1, len(height)):if height[i] < height[stack[-1]]:stack.append(i)# 当当前柱子高度和栈顶一致时,只需要保存一个柱子,作为凹槽底部高度的记录elif height[i] == height[stack[-1]]:continueelse:while stack and height[i] > height[stack[-1]]:mid_height = height[stack[-1]]stack.pop()if stack:right_height = height[i]left_height = height[stack[-1]]# 两侧的较矮一方的高度 - 凹槽底部高度h = min(right_height, left_height) - mid_heightw = i - stack[-1] - 1result += h * wstack.append(i)return result

 

相关文章:

代码随想录 单调栈part2

503. 下一个更大元素 II 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序&#xff0c;这个数字之后的第一个比它更大的数…...

详解利用高斯混合模型拆解多模态分布 + 精美可视化

文章目录 一、前言二、主要内容三、总结🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 本文旨在介绍如何利用高斯混合模型(Gaussian Mixture Models,简称 GMMs)将一维多模态分布拆分为多个分布。作为统计 / / /机器学习领域常用的概率模型...

排序算法之【归并排序】

&#x1f4d9;作者简介&#xff1a; 清水加冰&#xff0c;目前大二在读&#xff0c;正在学习C/C、Python、操作系统、数据库等。 &#x1f4d8;相关专栏&#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…...

Qt中QTimer定时器的用法

Qt中提供了两种定时器的方式一种是使用Qt中的事件处理函数&#xff0c;另一种就是Qt中的定时器类QTimer。 使用QTimer类&#xff0c;需要创建一个QTimer类对象&#xff0c;然后调用其start()方法开启定时器&#xff0c;此后QTimer对象就会周期性的发出timeout()信号。 1.QTimer…...

vue-组件定义注册使用

vue组件使用的步骤 定义组件注册组件使用组件 定义组件 Vue.extend(options) 其中options和new Vue(options)出入的options对象几乎一样&#xff0c;但是也有不同。 创建 el不用写—最终所有组件需要经过一个vm的管理&#xff0c;由vm的el决定服务哪个容器。 data必须写成函…...

斑馬打印機打印中文

创建项目 首先說一下&#xff0c;本文章是借鉴了其他大佬的文章&#xff0c;然后我记录一下的文章。 首先创建好一个.net framework的winform项目。 这里面主要用到两个库文件&#xff1a; Fnthex32.dll、LabelPrint.dll。 Fnthex32这个有8位参数和9位参数的&#xff0c;我这…...

(一)Apache log4net™ 手册 - 介绍

0、相关概念 Log4j 几乎每个大型应用程序都包含自己的日志记录或跟踪 API。根据这一规则&#xff0c;E.U. SEMPER &#x1f339;项目决定编写自己的跟踪 API。那是在 1996 年初。经过无数次的增强、几个化身和大量的工作&#xff0c;API 已经发展成为 log4j —— 一个流行的 Ja…...

基于Java的民宿管理系统设计与实现(源码+lw+部署文档+讲解等)(民宿预约、民宿预订、民宿管理、酒店预约通用)

文章目录 前言具体实现截图论文参考详细视频演示代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技…...

039:mapboxGL更换地图上的鼠标样式

第039个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中更换地图上的鼠标的样式。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共74行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:htt…...

【云原生】K8S对外服务之Ingress

目录 一、Ingress 简介1.1Ingress 组成1.3Ingress-Nginx 工作原理 二、部署 nginx-ingress-controller2.1部署ingress-controller Pod及相关资源2.2ingress 暴露服务的方式2.3 采用方式二&#xff1a;DaemonSetHostNetworknodeSelector 三、采用方式二&#xff1a;DeploymentNo…...

分布式锁如何实现

分布式是现在的比较主流的技术&#xff0c;常常和微服务一起出现。那么对于多个实例之间&#xff0c;如何证分布式系统中多个进程或线程同步访问共享资源呢&#xff1f;我们其实一想到的就是锁&#xff0c;我们在java里边有 synchronized, 在python里有lock&#xff0c;但是这个…...

Mysql存储-EAV模式

Mysql存储-EAV模式 最近又又又搞一点新东西&#xff0c;要整合不同业务进行存储和查询&#xff0c;一波学习过后总结了一下可扩展性MAX的eav模式存储。 在eav这里的数据结构设计尤为关键&#xff0c;需要充分考虑你需要使用的字段、使用场景&#xff0c;当数据结构设计完成后便…...

全局变量报错:\Output\STM32.axf: Error: L6218E: Undefined symbol

全局变量报错&#xff1a; .\Output\STM32.axf: Error: L6218E: Undefined symbol key_num (referred from main.o). 这里只说全局变量哦&#xff0c;这是因为你在调用的.c文件里 把定义写在了函数里面&#xff0c;写函数外面就没事了 改为&#xff1a; .h的声明文件根本不用写…...

算法错题簿(持续更新)

自用算法错题簿&#xff0c;按算法与数据结构分类 python1、二维矩阵&#xff1a;记忆化搜索dp2、图论&#xff1a;DFS3、回溯&#xff1a;129612964、二叉树&#xff1a;贪心算法5、字符串&#xff1a;记忆化搜索6、01字符串反转&#xff1a;结论题7、二进制数&#xff1a;逆向…...

基于Springboot实现疫情网课管理系统项目【项目源码+论文说明】

基于Springboot实现疫情网课管理系统演示 摘要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于疫情网课管理系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了疫情…...

Linux文件与目录的增删改查

一、增 1、mkdir命令 作用&#xff1a; 创建一个新目录。 格式&#xff1a; mkdir [选项] 要创建的目录 常用参数&#xff1a; -p&#xff1a;创建目录结构中指定的每一个目录&#xff0c;如果目录不存在则创建&#xff0c;如果目录已存在也不会被覆盖。 用法示例&a…...

JVM的内存模型

一、JVM的内存模型 1.1、目标 内存模型是用来描述JVM内部的内存结构和内存管理的模型。它定义了JVM在运行Java程序时所需要的各种内存区域&#xff0c;以及每个内存区域的作用和特点。 1.2、结构划分 1.2.1、栈 每个线程在执行Java方法时会创建一个栈帧&#xff08;Stack …...

数据采集项目之业务数据(三)

1. Maxwell框架 开发公司为Zendesk公司开源&#xff0c;用java编写的MySQL变更数据抓取软件。内部是通过监控MySQL的Binlog日志&#xff0c;并将变更数据以JSON格式发送到Kafka等流处理平台。 1.1 MySQL主从复制 主机每次变更数据都会生成对应的Binlog日志&#xff0c;从机可…...

vuedraggable影响点击事件的解决办法

在工作中有很多场景需要针对广告、商品、信息推广等进行一个排序,或者对展示的顺序做出调整,方便放用户第一眼看到自己感兴趣的信息,因此避免不了需要用到排序的插件,这里以vue为例子,采用的插件是vuedraggable,这个插件针对于排序的功能相对完善,官网地址:vuedraggable官网 但…...

Linux 中的 grep 命令

Linux 中的 grep 命令是一个强大的文本搜索工具&#xff0c;它允许用户在文件中查找指定的文本模式&#xff0c;并将匹配的行打印出来。grep 是“Global Regular Expression Print”的缩写&#xff0c;它使用正则表达式来进行文本搜索&#xff0c;因此具有强大的灵活性和功能。…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...