代码随想录 单调栈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 ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数…...
详解利用高斯混合模型拆解多模态分布 + 精美可视化
文章目录 一、前言二、主要内容三、总结🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 本文旨在介绍如何利用高斯混合模型(Gaussian Mixture Models,简称 GMMs)将一维多模态分布拆分为多个分布。作为统计 / / /机器学习领域常用的概率模型...

排序算法之【归并排序】
📙作者简介: 清水加冰,目前大二在读,正在学习C/C、Python、操作系统、数据库等。 📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍…...

Qt中QTimer定时器的用法
Qt中提供了两种定时器的方式一种是使用Qt中的事件处理函数,另一种就是Qt中的定时器类QTimer。 使用QTimer类,需要创建一个QTimer类对象,然后调用其start()方法开启定时器,此后QTimer对象就会周期性的发出timeout()信号。 1.QTimer…...
vue-组件定义注册使用
vue组件使用的步骤 定义组件注册组件使用组件 定义组件 Vue.extend(options) 其中options和new Vue(options)出入的options对象几乎一样,但是也有不同。 创建 el不用写—最终所有组件需要经过一个vm的管理,由vm的el决定服务哪个容器。 data必须写成函…...

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

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

基于Java的民宿管理系统设计与实现(源码+lw+部署文档+讲解等)(民宿预约、民宿预订、民宿管理、酒店预约通用)
文章目录 前言具体实现截图论文参考详细视频演示代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者,博客之星、掘金/华为云/阿里云/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 采用方式二:DaemonSetHostNetworknodeSelector 三、采用方式二:DeploymentNo…...

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

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

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

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

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

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

JVM的内存模型
一、JVM的内存模型 1.1、目标 内存模型是用来描述JVM内部的内存结构和内存管理的模型。它定义了JVM在运行Java程序时所需要的各种内存区域,以及每个内存区域的作用和特点。 1.2、结构划分 1.2.1、栈 每个线程在执行Java方法时会创建一个栈帧(Stack …...
数据采集项目之业务数据(三)
1. Maxwell框架 开发公司为Zendesk公司开源,用java编写的MySQL变更数据抓取软件。内部是通过监控MySQL的Binlog日志,并将变更数据以JSON格式发送到Kafka等流处理平台。 1.1 MySQL主从复制 主机每次变更数据都会生成对应的Binlog日志,从机可…...
vuedraggable影响点击事件的解决办法
在工作中有很多场景需要针对广告、商品、信息推广等进行一个排序,或者对展示的顺序做出调整,方便放用户第一眼看到自己感兴趣的信息,因此避免不了需要用到排序的插件,这里以vue为例子,采用的插件是vuedraggable,这个插件针对于排序的功能相对完善,官网地址:vuedraggable官网 但…...
Linux 中的 grep 命令
Linux 中的 grep 命令是一个强大的文本搜索工具,它允许用户在文件中查找指定的文本模式,并将匹配的行打印出来。grep 是“Global Regular Expression Print”的缩写,它使用正则表达式来进行文本搜索,因此具有强大的灵活性和功能。…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
【题解-洛谷】P10480 可达性统计
题目:P10480 可达性统计 题目描述 给定一张 N N N 个点 M M M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。 输入格式 第一行两个整数 N , M N,M N,M,接下来 M M M 行每行两个整数 x , y x,y x,y,表示从 …...