代码随想录 单调栈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”的缩写,它使用正则表达式来进行文本搜索,因此具有强大的灵活性和功能。…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...