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

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.length
  • 1 <= n <= 2 * 104
  • 0 <= 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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…...

Python学习阶段路线和内容

Python学习阶段路线和内容 这是我的看法和认识&#xff0c;供参考。 Python学习路线主要分为三个阶段&#xff1a;入门阶段、提高阶段和深入阶段。 入门阶段 入门阶段需要学习Python的基本语法&#xff0c;掌握变量和数据类型、条件语句和循环语句、函数和模块等内容。并通过…...

RocketMQ教程-安装和配置

Linux系统安装配置 64位操作系统&#xff0c;推荐 Linux/Unix/macOS 64位 JDK 1.8 Maven3.0 yum 安装jdk8 yum 安装maven 1.下载安装Apache RocketMQ RocketMQ 的安装包分为两种&#xff0c;二进制包和源码包。 点击这里 下载 Apache RocketMQ 5.1.3的源码包。你也可以从这…...

【LeetCode】55.跳跃游戏

题目 给定一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1&#xff1a; 输入&#xff1a;nums [2,3,1,1,4] 输出&#xff1a;true 解释&#xff1a;可以…...

Docker学习路线12:开发者体验

到目前为止&#xff0c;我们只讨论了使用Docker来部署应用程序。然而&#xff0c;Docker也是一个极好的用于开发应用程序的工具。可以采用一些不同的建议来改善开发体验。 在应用程序中使用docker-compose以方便开发。使用绑定挂载将本地代码挂载到容器文件系统中&#xff0c;…...

后端服务迁移方案及过程记录

阶段时序动作双写数据对比1新rdb集群上线双写数据对比2新服务上线&#xff0c;无流量双写数据对比2后端自己发起的流程比如job&#xff0c;新服务上线一份新的&#xff0c;独立运行双写数据对比2消费二方mq&#xff0c;新服务使用新的消费组消费原有消息双写数据对比3新旧服务比…...

StAX解析

StAX解析 StAX解析介绍 StAX解析与SAX解析类似&#xff0c;也是基于事件驱动的&#xff0c;不同之处在于StAX采用的是拉模式&#xff0c;应用程序通过调用解析器推进解析的进程&#xff0c;可以调用next()方法来获取下一个解析事件(开始文档&#xff0c;结束文档&#xff0c;开…...

[MCU]AUTOSAR COM STACK - CAN协议栈

各层PDU PDU&#xff1a;Protocal Data Unit&#xff0c;协议数据单元&#xff0c;由SDU和PCI组成&#xff1b; I-PDU&#xff1a;Interaction Layer PDU&#xff0c;数据交互层PDU&#xff1b;N-PDU&#xff1a;NetWork Layer PDU&#xff0c;网络层PDU&#xff0c;通常用的…...

React:从 npx开始

使用 npm 来创建第一个 recat 文件&#xff08; react-demo 是文件名&#xff0c;可以自定义&#xff09; npx create-react-app react-demo npx是 npm v5.2 版本新添加的命令&#xff0c;用来简化 npm 中工具包的使用 原始&#xff1a; 全局安装npm i -g create-react-app 2 …...

力扣热门100题之接雨水【困难】

题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…...

Stable-Diffusion-Webui部署SDXL0.9报错参数shape不匹配解决

问题 已经在model/stable-diffusion文件夹下放进去了sdxl0.9的safetensor文件&#xff0c;但是在切换model的时候&#xff0c;会报错model的shape不一致。 解决方法 git pullupdate一些web-ui项目就可以&#xff0c;因为当前项目太老了&#xff0c;没有使用最新的版本。...

Springboot @Async 多线程获取返回值

Springboot Async 多线程获取返回值 需求背景 最近需要用到多线程, 自己维护线程池很麻烦, 正好看到Springboot集成线程池的例子, 这里自己做了个尝试和总结, 记录一下, 也分享给需要的朋友; 不考虑事务的情况下, 这个多线程实现比较简单, 主要有以下几点: 在启动类加上Enab…...

怎样接入chatGPT

官网链接&#xff1a; OpenAI platform...

Docker consul容器服务更新与发现

Docker consul容器服务更新与发现 一、什么事服务注册与发现二、什么是consul三、consul部署1、consul服务器2、registrator服务器3、consul-template 一、什么事服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的&#xff0c;不保障高可…...

[算法很美打卡] 多维数组篇 (打卡第一天)

文章目录 顺时针打印二维数组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?

微服务系列&#xff08;1&#xff09;-我是谁 应用架构的演化 简单来说系统架构可以分为以下几个阶段&#xff1a;复杂的臃肿的单体架构-SOA架构-微服务 单体架构及其所面临的问题 在互联网发展初期&#xff0c;用户数量少&#xff0c;流量小&#xff0c;硬件成本高。因此…...

记录这这段时间发生的事情。

当做后端的时候总是被骂做前很丑。成为一个UI设计师与后端工程师才会更加完美。 尝试着做一个主页面。 创建了一个主页面 的表格index。 收录了希望发送到主页的&#xff0c;的帖子。 并且&#xff0c;可以填写是否可以。 一个看起来不错的主页。 标题设计的左右框。 这种框…...

发布npm包流程

发布npm包的步骤如下&#xff1a; 在终端中通过 npm init 命令创建一个新的npm包&#xff0c;按照提示填写包的信息&#xff0c;如包名称、版本、描述、作者、许可证等。 在包的根目录下创建一个 index.js 文件&#xff0c;编写你的代码。 确认你已经注册了npm账号&#xff0…...

面试官:Redis 为什么变慢了?怎么解决?

一、Redis为什么变慢了 二、Redis如何优化 三、Redis变慢了排查步骤 一、Redis为什么变慢了 1.Redis真的变慢了吗&#xff1f; 对 Redis 进行基准性能测试 例如&#xff0c;我的机器配置比较低&#xff0c;当延迟为 2ms 时&#xff0c;我就认为 Redis 变慢了&#xff0c;…...

Docker:开启应用程序开发新篇章的利器

Docker&#xff1a;开启应用程序开发新篇章的利器 引言&#xff1a;1. Docker 的基本概念2. Docker 的优势3. Docker 在应用程序开发中的实际应用如何创建docker镜像如何部署docker镜像结论&#xff1a; 引言&#xff1a; 在现代软件开发领域中&#xff0c;容器化技术正在迅猛…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

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

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

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...