代码随想录 单调栈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”的缩写,它使用正则表达式来进行文本搜索,因此具有强大的灵活性和功能。…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
