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

入门力扣自学笔记277 C++ (题目编号:42)(动态规划)

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 * 10^{4}
  • 0 <= height[i] <= 10^{5}

思路:

首先,获取数组长度。

其次,获取每一个点的左侧和右侧的最大高度。

最后,找到每一个点左侧和右侧最大高度较小的那个(因为只有较小的那个高度才能限制雨水容量)。将这个减去该位置的高度,即可得到该位置的雨水单位数,将其累加到最终结果中。


代码:

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);//cout << leftMax[i] << '|';}//cout << endl;vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);//cout << rightMax[i] << '|';}//cout << endl;int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];//cout << min(leftMax[i], rightMax[i]) - height[i] << '|';}return ans;}
};

 

相关文章:

入门力扣自学笔记277 C++ (题目编号:42)(动态规划)

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

SwiftUI实现iPad多任务分屏

1. 概述 iPadOS引入了多任务分屏功能&#xff0c;使用户能够同时在一个屏幕上使用多个应用程序。这为用户提供了更高效的工作环境&#xff0c;可以在同一时间处理多个任务。 iPad多任务分屏有两种常见的模式&#xff1a;1/2分屏和Slide Over&#xff08;滑动覆盖&#xff09;…...

maven依赖,继承

依赖的范围 compile引入的依赖 对main目录下的代码有没有效&#xff0c;main目录下的代码能不能用compile引入的依赖中的类等 以test引入的依赖&#xff0c;在main中是否可以使用 provided&#xff08;已提供&#xff09;&#xff0c;有了就不要带到服务器上&#xff0c;打包…...

仿`gRPC`功能实现像调用本地方法一样调用其他服务器方法

文章目录 仿gRPC功能实现像调用本地方法一样调用其他服务器方法 简介单体架构微服务架构RPCgPRC gRPC交互逻辑服务端逻辑客户端逻辑示例图 原生实现仿gRPC框架编写客户端方法编写服务端方法综合演示 仿 gRPC功能实现像调用本地方法一样调用其他服务器方法 简介 在介绍gRPC简介…...

分布式环境下的数据同步

一般而言elasticsearch负责搜索&#xff08;查询&#xff09;&#xff0c;而sql数据负责记录&#xff08;增删改&#xff09;&#xff0c;elasticsearch中的数据来自于sql数据库&#xff0c;因此sql数据发生改变时&#xff0c;elasticsearch也必须跟着改变&#xff0c;这个就是…...

无涯教程-Flutter - 数据库

SQLite" class"css-1occaib">SQLite数据库是基于事实和标准SQL的嵌入式数据库引擎&#xff0c;它是小型且经过时间考验的数据库引擎&#xff0c;sqflite软件包提供了许多函数&#xff0c;可以有效地与SQLite数据库一起使用&#xff0c;它提供了操作SQLite数据…...

算法笔记:平衡二叉树

1 介绍 平衡二叉树&#xff08;AVL树&#xff09;是一种特殊的二叉搜索树&#xff08;BST&#xff09;&#xff0c;它自动确保树保持低高度&#xff0c;以便实现各种基本操作&#xff08;如添加、删除和查找&#xff09;的高效性能。 ——>时间都维持在了O(logN)它是一棵空…...

redis 通用命令

目录 通用命令是什么 SET & GET keys EXISTS DEL EXPIRE TTL redis 的过期策略 定时器策略 基于优先级队列定时器 基于时间轮的定时器 TYPE 通过 redis 客户端和 redis 服务器交互。 所以需要使用 redis 的命令&#xff0c;但是 redis 的命令非常多。 通用命令…...

Pycharm配置及使用Git教程

文章目录 1. 安装PyCharm2. 安装Git3. 在PyCharm中配置Git插件4. 连接远程Gtilab仓库5. Clone项目代码6. 将本地文件提交到远程仓库6.1 git add6.2 git commit6.3 git push6.4 git pull 平时习惯在windows下开发&#xff0c;但是我们又需要实时将远方仓库的代码clone到本地&…...

CSS transition 过渡

1 前言 水平居中、垂直居中是前端面试百问不厌的问题。 其实现方案也是多种多样&#xff0c;常叫人头昏眼花。 水平方向可以认为是内联方向&#xff0c;垂直方向认为是块级方向。 下面介绍一些常见的方法。 2 内联元素的水平垂直居中 首先&#xff0c;常见内联元素有&…...

Unity中Shader的UV扭曲效果的实现

文章目录 前言一、实现的思路1、在属性面板暴露一个 扭曲贴图的属性2、在片元结构体中&#xff0c;新增一个float2类型的变量&#xff0c;用于独立存储将用于扭曲的纹理的信息3、在顶点着色器中&#xff0c;根据需要使用TRANSFORM_TEX对Tilling 和 Offset 插值&#xff1b;以及…...

Automotive 添加一个特权APP

Automotive 添加一个特权APP platform: android-13.0.0_r32 一. 添加一个自定义空调的app为例 路径&#xff1a;packages/apps/Car/MyHvac app内容可以自己定义&#xff0c;目录结构如下&#xff1a; 1.1 Android.bp package {default_applicable_licenses: ["Andr…...

自定义TimeLine

自定义TimeLine 什么是TimeLineData&#xff08;数据&#xff09;Clip&#xff08;片段&#xff09;Track&#xff08;轨道&#xff09;Mixer&#xff08;混合&#xff09; 什么是TimeLine 在 Unity 中&#xff0c;TimeLine&#xff08;时间轴&#xff09;是一种用于创建和管理…...

如何使用SQL系列 之 如何在SQL中使用WHERE条件语句

引言 在结构化查询语言 (SQL)语句中&#xff0c;WHERE子句限制了给定操作会影响哪些行。它们通过定义特定的条件(称为搜索条件)来实现这一点&#xff0c;每一行都必须满足这些条件才能受到操作的影响。 本指南将介绍WHERE子句中使用的通用语法。它还将概述如何在单个WHERE子句…...

leetcode:1941. 检查是否所有字符出现次数相同(python3解法)

难度&#xff1a;简单 给你一个字符串 s &#xff0c;如果 s 是一个 好 字符串&#xff0c;请你返回 true &#xff0c;否则请返回 false 。 如果 s 中出现过的 所有 字符的出现次数 相同 &#xff0c;那么我们称字符串 s 是 好 字符串。 示例 1&#xff1a; 输入&#xff1a;s…...

Echarts 各种点击事件监听

目录 一、鼠标事件1.1、左击1.2、双击1.3、右击1.4、右键双击1.5、中轴滚动二、时间轴2.1、时间轴监听三、拖动3.1、拖动事件一、鼠标事件 1.1、左击 chart.on(click, function(params)...

《智能网联汽车自动驾驶功能测试规程》

一、 编制背景 2018 年4 月12 日&#xff0c;工业和信息化部、公安部、交通运输部联合发布《智能网联汽车道路测试管理规范(试行)》&#xff08;以下简称《管理规范》&#xff09;&#xff0c;对智能网联汽车道路测试申请、审核、管理以及测试主体、测试驾驶人和测试车辆要求等…...

NVIDIA CUDA Win10安装步骤

前言 windows10 版本安装 CUDA &#xff0c;首先需要下载两个安装包 CUDA toolkit&#xff08;toolkit就是指工具包&#xff09;cuDNN 1. 安装前准备 在安装CUDA之前&#xff0c;需要完成以下准备工作&#xff1a; 确认你的显卡已经正确安装&#xff0c;在设备管理器中可以看…...

Elasticsearch、Kibana以及Java操作ES 的快速使用

docker 安装elastic search 、 kibana&#xff08;可视化管理elastic search&#xff09; docker pull elasticsearch:7.12.1 docker pull kibana:7.12.1创建docker自定义网络 docker自定义网络可以使得容器之间使用容器名网络互连&#xff0c;默认的网络不会有这功能。 一定…...

逐鹿人形机器人,百度、腾讯、小米卷起来

长期不温不火的人形机器人产业迎来新风口&#xff0c;技术显著提升、新品层出不穷、资本投资态度也逐渐好转。 8月18日&#xff0c;2023世界机器人大会博览会正式开放&#xff0c;全面展示了机器人行业的新技术、新产品和新应用。据悉&#xff0c;此次展会展览总面积达4.5万平…...

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

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

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...