【前缀和】42. 接雨水
本文涉及知识点
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode42. 接雨水
给定 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
枚举
vWater[i] 记录 第i个柱子水的高度。
令 leftMax =max(height[0…i-1])
rightMax = max(height[i+1…])
如果水高于 leftMax 或 rightMax,水会流走。故水的高度为:min(leftMax,rightMax) - height[i]
结果为负,则为0。
更改leftMax为max(height[0…i]),rightMax类似。则不需要考虑负数。
时间复杂度:O(n)
代码
核心代码
class Solution {
public:int trap(vector<int>& height) {const int n = height.size();vector<int> vLeft = height;for (int i = 1; i < n; i++) {vLeft[i] = max(vLeft[i], vLeft[i - 1]);}int iRightMax = 0;int iRet = 0;for (int i = n - 1; i >= 0; i--) {iRightMax = max(iRightMax, height[i]);const int iWater = min(iRightMax, vLeft[i]);iRet += iWater - height[i];}return iRet;}
};
单元测试
template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> height;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){ height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };auto res = Solution().trap(height);AssertEx(6,res);}TEST_METHOD(TestMethod1){height = { 4, 2, 0, 3, 2, 5 };auto res = Solution().trap(height);AssertEx(9, res);}};
}

扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【前缀和】42. 接雨水
本文涉及知识点 C算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入&am…...
我的名字叫大数据
第1章 大家好,我叫大数据 1.1 我的家族传统:从我小小的祖先到壮大的我 1.1.1 最初的我:原始部落里的计数石头 大家好,我是你们人类文明的“老朋友”——大数据。你们知道吗?在我还没有变成你们手机、电脑里飞速跑动的那些数字前,我最初的模样可是一块块“计数石头”。…...
数据库漫谈-infomix
infomix数据库知名度不高,主要跟它的定位有关,它主要用于unix操作系统:Informix便是取自Information和Unix的结合,它也是第一个支持linux系统的数据库。它其实在金融、电信行业使用率非常高。98年,当时我在做银行领域的…...
【Qt】Qt界面美化指南:深入理解QSS样式表的应用与实践
文章目录 前言:1. 背景介绍2. 基本语法3. QSS 设置方式3.1. 设置全局样式3.2. 从文件加载样式表3.3. 使用 Qt Designer 编辑样式 总结: 前言: 在当今这个视觉至上的时代,用户界面(UI)的设计对于任何软件产…...
七彩云南文化旅游网站的设计
管理员账户功能包括:系统首页,个人中心,管理员管理,游客管理,导游管理,旅游景点管理,酒店信息管理 前台账户功能包括:系统首页,个人中心,论坛,旅…...
7-zip安装教程
一、简介 7-Zip 是一款开源的文件压缩软件,由 Igor Pavlov 开发。它具有高压缩比、支持多种格式、跨平台等特点。使用 C语言编写,其代码在 Github 上开源。 7-Zip的官网: 7-Zip 7-zip官方中文网站: 7-Zip 官方中文网站 7-Zip 的 G…...
oracle 12c DB卸载流程
1.运行卸载程序 [rootprimary1 ~]# su - oracle [oracleprimary1 ~]$ cd $ORACLE_HOME/deinstall [oracleprimary1 deinstall]$ ./deinstall Checking for required files and bootstrapping ... Please wait ... 这里选择3 、回车、y、y、回车、ASM 这里输入y 2.删除相关目录…...
Docker学习笔记 - 创建自己的image
目录 基本概念常用命令使用docker compose启动脚本创建自己的image 使用Docker是现在最为流行的软件发布方式, 本系列将阐述Docker的基本概念,常用命令,启动脚本和如何生产自己的docker image。 在我们发布软件时,往往需要把我…...
java web爬虫
目录 读取本地文件 从网站读取文件 java爬虫 总结 读取本地文件 import java.io.File; import java.io.PrintWriter; import java.util.Scanner;public class ReplaceText {public static void main() throws Exception{File file new File("basic\\test.txt"…...
MySQL开发教程和具体应用案例
一、MySQL开发教程 初识数据库 定义:数据仓库,安装在操作系统之上,用于存储和管理数据。 分类:关系型数据库(如MySQL、Oracle、SQL Server)和非关系型数据库(如Redis、MongoDB)。 SQL:结构化查询语言,用于管理和操作关系型数据库。 操作数据库 创建、修改、删除…...
QT C++ 模型视图结构 QTableView 简单例子
在Qt中,MVC模式被广泛使用于各种用户界面框架中,包括Qt的模型视图结构。Qt的模型视图结构是基于MVC模式设计的,其中包括了Model、View和Delegate三个部分。 QTableView是Qt模型视图结构中的一种视图,它用于以表格形式显示数据。 …...
2024年3月电子学会Python编程等级考试(四级)真题题库
2024年3月青少年软件编程Python等级考试(四级)真题试卷 题目总数:38 总分数:100 选择题 第 1 题 单选题 运行如下Python代码,若输入整数3,则最终输出的结果为?( ÿ…...
深入分析 Android BroadcastReceiver (一)
文章目录 深入分析 Android BroadcastReceiver (一)1. Android BroadcastReceiver 设计说明1.1 BroadcastReceiver 的主要用途 2. BroadcastReceiver 的工作机制2.1 注册 BroadcastReceiver2.1.1 静态注册2.1.2 动态注册 3. BroadcastReceiver 的生命周期4. 实现和使用 Broadca…...
2024医美如何做抖音医美抖音号,本地团购、短视频直播双ip爆品引流,实操落地课
课程下载:https://download.csdn.net/download/m0_66047725/89307619 更多资源下载:关注我。 课程内容: 01-0-序.mp4 02-01-账号定位.mp4 03-02-误区.mp4 04-03-五件套.mp4 05-04-文案怎么来.mp4 06-05-对标怎么弄.mp4 07-06-人设怎…...
Debian常用指令指南:高效管理你的Linux系统
Debian作为Linux发行版中的佼佼者,以其稳定性和安全性而闻名。掌握Debian的常用指令对于系统管理员和开发人员来说至关重要。本文将介绍一系列Debian系统中的常用指令,帮助你高效地管理和维护你的系统。喜欢的话记得一键三连哦,方便找到它。 …...
什么是DELINS交货指示?
DELINS 是指 Delivery Instruction(交货指示)报文,用于在供应链管理中传递交货指令和相关信息。该报文用于在供应链中的不同合作伙伴之间交换关于交货的详细信息。 DELINS 报文的主要功能 交货指示:传达具体的交货指令ÿ…...
基于Open3D的点云处理24-ICP匹配cuda加速
参考:docs/jupyter/t_pipelines/t_icp_registration.ipynb 完整测试用例: import open3d as o3d import open3d.core as o3cif o3d.__DEVICE_API__ == cuda:import open3d.cuda.pybind.t.pipelines.registration as treg else:...
UE_地编教程_创建地形洞材质
个人学习笔记,不喜勿喷。侵权立删! 使用地形洞材质来遮罩地形上特定位置的可视性和碰撞。如要在山脉侧面创建进入洞穴的入口,此操作将非常有用。可使用地形材质和地形洞材质的相同材质,但注意:对比不使用不透明蒙版的…...
「C系列」C 基本语法
文章目录 一、C 基本语法1. **程序结构**2. **数据类型**3. **变量声明**4. **运算符**6. **函数**7. **指针**8. **数组**9. **结构体和联合体**10. **预处理指令**11. **内存管理** 二、C 关键字1. 整体概览2. 具体关键字数据类型关键字控制流关键字其他关键字C11新增关键字总…...
java期末细节知识整理(一)
1.java程序的执行过程:先编译后解释。也就是我们在idea写的文件叫做java源文件(.java结尾的文件),经过编译器会生成字节码文件(.class结尾的文件),再通过解释器进行实现 2.栈用来存储引用类型的…...
AXI Quad SPI IP核在多主设备环境下的三态总线设计与实现
1. AXI Quad SPI IP核的多主设备挑战 第一次接触AXI Quad SPI IP核的多主设备配置时,我踩过一个典型的坑:两个FPGA内部主模块同时向SPI总线发送数据,导致MOSI信号出现毛刺。这种情况在共享总线架构中非常常见,而三态总线设计正是解…...
计算机毕设 java 基于 Javaweb 的家教管理系统 智能家教匹配管理系统 家教服务综合平台
计算机毕设 java 基于 Javaweb 的家教管理系统 f7xm39(配套有源码 程序 mysql 数据库 论文)本套源码可以先看具体功能演示视频领取,文末有联 xi 可分享随着家庭教育需求的不断增长,家教市场规模持续扩大,但传统家教模式…...
MongoDB时间戳转换实战:从数字到标准时间格式的完整指南
1. MongoDB时间戳转换的核心概念 第一次接触MongoDB时间戳转换时,我也被各种时间格式搞得晕头转向。简单来说,MongoDB中的时间戳主要有三种存储形式:数字类型(如1655448286502)、字符串类型(如"165544…...
Spring Cloud Hystrix 详细示-元一软件
Hystrix 是 Spring Cloud 中实现服务熔断、降级、隔离的核心组件,用于解决微服务架构中的雪崩效应,核心是快速失败、优雅降级、自动恢复。以下从环境搭建、基础使用、高级配置、Feign 整合、监控5 个维度提供完整示例。一、项目环境准备1. 依赖引入&…...
嵌入式硬件设计核心要点与实战技巧
嵌入式硬件设计关键要点解析1. 嵌入式系统硬件架构概述嵌入式系统的硬件架构以CPU为核心,所有外围设备都围绕CPU进行配置。这种架构最显著的特点是硬件可裁剪性,设计者可以根据具体应用需求灵活调整系统组成。在典型的嵌入式硬件设计中,需要重…...
轻量级涨点神器:Ghost卷积模块在YOLOv8中的实战应用与性能优化
1. Ghost卷积模块:轻量化的秘密武器 第一次听说Ghost卷积时,我正为一个嵌入式设备上的目标检测项目发愁。当时需要在树莓派上部署YOLOv3,但模型跑起来像老牛拉车,帧率直接掉到个位数。直到试用了Ghost模块,推理速度直接…...
解锁小米平板5的Windows潜能:从Android平板到完整PC体验的驱动革命
解锁小米平板5的Windows潜能:从Android平板到完整PC体验的驱动革命 【免费下载链接】MiPad5-Drivers Based on Surface Duo Drivers. 项目地址: https://gitcode.com/gh_mirrors/mi/MiPad5-Drivers 你是否曾想过,将手中的小米平板5从一台Android设…...
OptiScaler终极配置指南:解锁游戏画质提升的7个关键技术
OptiScaler终极配置指南:解锁游戏画质提升的7个关键技术 【免费下载链接】OptiScaler DLSS replacement for AMD/Intel/Nvidia cards with multiple upscalers (XeSS/FSR2/DLSS) 项目地址: https://gitcode.com/GitHub_Trending/op/OptiScaler OptiScaler是一…...
Rust Desk自建服务器全攻略:从零搭建比向日葵更快的远程桌面(附密钥配置避坑指南)
Rust Desk私有化部署实战:构建高性能远程桌面的完整指南 远程协作工具已成为现代办公的标配,但主流商业方案往往存在延迟高、隐私风险等问题。Rust Desk作为开源解决方案,不仅提供媲美商业软件的功能体验,更通过私有化部署实现完全…...
突破Windows权限限制:TrustedInstaller提权工具完全指南
突破Windows权限限制:TrustedInstaller提权工具完全指南 【免费下载链接】LeanAndMean snippets for power users 项目地址: https://gitcode.com/gh_mirrors/le/LeanAndMean 作为系统管理员或高级用户,你是否曾因"拒绝访问"而无法修改…...
