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

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
解答
C++解法
class Solution {
public:int trap(vector<int>& height) {// 双指针 前后最大值// 每个位置左边和右边最高高度分别记录在数组上// 每个位置可以储水的容量取决于其左右两边最大值之小者if(height.size() <= 2) return 0;vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = maxRight.size();// 记录每个柱子左边的最大高度maxLeft[0] = height[0];for(int i = 1; i < size; ++i){maxLeft[i] = max(maxLeft[i - 1], height[i]);}maxRight[size - 1] = height[size - 1];for(int i = size - 2; i >= 0; --i){maxRight[i] = max(maxRight[i + 1], height[i]);}int res = 0;for(int i = 1; i < size; ++i){res += min(maxRight[i], maxLeft[i]) - height[i];}return res;}
};
python3
class Solution:# 每一个位置能盛放多少水取决于其左边和右边柱子的最大高度的小者def trap(self, height: List[int]) -> int:n = len(height)# pre_max[i] 表示下标为i的柱子前面(包括下标为i的柱子)的最大高度pre_max = [0] * npre_max[0] = height[0] for i in range(1, n):pre_max[i] = max(pre_max[i - 1], height[i])# suf_max[i] 表示下标为i的柱子(包括下标为i的柱子)后面的最大高度suf_max = [0] * nsuf_max[-1] = height[-1]#n-2 ~ 0 for i in range(n - 2, -1, -1):suf_max[i] = max(suf_max[i + 1], height[i])ans = 0# zip 将其中的列表打包成元组的列表用来迭代for h, pre, suf in zip(height, pre_max, suf_max):ans += min(pre, suf) - hreturn ans
相关文章:
42. 接雨水
题目介绍 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3…...
Python学习阶段路线和内容
Python学习阶段路线和内容 这是我的看法和认识,供参考。 Python学习路线主要分为三个阶段:入门阶段、提高阶段和深入阶段。 入门阶段 入门阶段需要学习Python的基本语法,掌握变量和数据类型、条件语句和循环语句、函数和模块等内容。并通过…...
RocketMQ教程-安装和配置
Linux系统安装配置 64位操作系统,推荐 Linux/Unix/macOS 64位 JDK 1.8 Maven3.0 yum 安装jdk8 yum 安装maven 1.下载安装Apache RocketMQ RocketMQ 的安装包分为两种,二进制包和源码包。 点击这里 下载 Apache RocketMQ 5.1.3的源码包。你也可以从这…...
【LeetCode】55.跳跃游戏
题目 给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 输入:nums [2,3,1,1,4] 输出:true 解释:可以…...
Docker学习路线12:开发者体验
到目前为止,我们只讨论了使用Docker来部署应用程序。然而,Docker也是一个极好的用于开发应用程序的工具。可以采用一些不同的建议来改善开发体验。 在应用程序中使用docker-compose以方便开发。使用绑定挂载将本地代码挂载到容器文件系统中,…...
后端服务迁移方案及过程记录
阶段时序动作双写数据对比1新rdb集群上线双写数据对比2新服务上线,无流量双写数据对比2后端自己发起的流程比如job,新服务上线一份新的,独立运行双写数据对比2消费二方mq,新服务使用新的消费组消费原有消息双写数据对比3新旧服务比…...
StAX解析
StAX解析 StAX解析介绍 StAX解析与SAX解析类似,也是基于事件驱动的,不同之处在于StAX采用的是拉模式,应用程序通过调用解析器推进解析的进程,可以调用next()方法来获取下一个解析事件(开始文档,结束文档,开…...
[MCU]AUTOSAR COM STACK - CAN协议栈
各层PDU PDU:Protocal Data Unit,协议数据单元,由SDU和PCI组成; I-PDU:Interaction Layer PDU,数据交互层PDU;N-PDU:NetWork Layer PDU,网络层PDU,通常用的…...
React:从 npx开始
使用 npm 来创建第一个 recat 文件( react-demo 是文件名,可以自定义) npx create-react-app react-demo npx是 npm v5.2 版本新添加的命令,用来简化 npm 中工具包的使用 原始: 全局安装npm i -g create-react-app 2 …...
力扣热门100题之接雨水【困难】
题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3…...
Stable-Diffusion-Webui部署SDXL0.9报错参数shape不匹配解决
问题 已经在model/stable-diffusion文件夹下放进去了sdxl0.9的safetensor文件,但是在切换model的时候,会报错model的shape不一致。 解决方法 git pullupdate一些web-ui项目就可以,因为当前项目太老了,没有使用最新的版本。...
Springboot @Async 多线程获取返回值
Springboot Async 多线程获取返回值 需求背景 最近需要用到多线程, 自己维护线程池很麻烦, 正好看到Springboot集成线程池的例子, 这里自己做了个尝试和总结, 记录一下, 也分享给需要的朋友; 不考虑事务的情况下, 这个多线程实现比较简单, 主要有以下几点: 在启动类加上Enab…...
怎样接入chatGPT
官网链接: OpenAI platform...
Docker consul容器服务更新与发现
Docker consul容器服务更新与发现 一、什么事服务注册与发现二、什么是consul三、consul部署1、consul服务器2、registrator服务器3、consul-template 一、什么事服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的,不保障高可…...
[算法很美打卡] 多维数组篇 (打卡第一天)
文章目录 顺时针打印二维数组0所在的行列清零 顺时针打印二维数组 package 每日算法学习打卡.算法打卡.七月份.七月二十六号;public class test1 {public static void main(String[] args) {int[][] matrix {{1,2},{5,6},{9,10},{13,14},};print(matrix);}static void print(i…...
微服务系列(1)-who i am?
微服务系列(1)-我是谁 应用架构的演化 简单来说系统架构可以分为以下几个阶段:复杂的臃肿的单体架构-SOA架构-微服务 单体架构及其所面临的问题 在互联网发展初期,用户数量少,流量小,硬件成本高。因此…...
记录这这段时间发生的事情。
当做后端的时候总是被骂做前很丑。成为一个UI设计师与后端工程师才会更加完美。 尝试着做一个主页面。 创建了一个主页面 的表格index。 收录了希望发送到主页的,的帖子。 并且,可以填写是否可以。 一个看起来不错的主页。 标题设计的左右框。 这种框…...
发布npm包流程
发布npm包的步骤如下: 在终端中通过 npm init 命令创建一个新的npm包,按照提示填写包的信息,如包名称、版本、描述、作者、许可证等。 在包的根目录下创建一个 index.js 文件,编写你的代码。 确认你已经注册了npm账号࿰…...
面试官:Redis 为什么变慢了?怎么解决?
一、Redis为什么变慢了 二、Redis如何优化 三、Redis变慢了排查步骤 一、Redis为什么变慢了 1.Redis真的变慢了吗? 对 Redis 进行基准性能测试 例如,我的机器配置比较低,当延迟为 2ms 时,我就认为 Redis 变慢了,…...
Docker:开启应用程序开发新篇章的利器
Docker:开启应用程序开发新篇章的利器 引言:1. Docker 的基本概念2. Docker 的优势3. Docker 在应用程序开发中的实际应用如何创建docker镜像如何部署docker镜像结论: 引言: 在现代软件开发领域中,容器化技术正在迅猛…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
