当前位置: 首页 > 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万平…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...