手撕算法-接雨水

描述

image.png

分析

i位置能积累的雨水量,等于其左右两边最大高度的最小值。
为了能获取i位置左右两边的最大高度。使用动态规划。
两个dp数组:

  • leftMax
  • rightMax

其中

  • leftMax[i] 代表i位置左边的最大高度
  • rightMax[i] 代表i位置右边的最大高度

初始状态:

  • leftMax[0] = 0;
  • rightMax[0] =0;

填充这两个dp数组。

那么i位置最终能存的雨水量为:min(eftMax[i] , rightMax[i]) - height[i]

遍历所有位置,即可得到总共能接的雨水数。

image.png

代码

class Solution {public int trap(int[] height) {int n = height.length;int[] leftMax = new int[n];int[] rightMax = new int[n];leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}int res = 0;for (int i = 0; i < n; i++) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}

image.png

面试公司

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/283511.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Nacos源码流程图

1.Nacos1.x版本服务注册与发现源码 流程图地址&#xff1a;https://www.processon.com/view/link/634695eb260d7157a7bc6adb 2.Nacos2.x版本服务注册与发现源码 流程图地址&#xff1a;https://www.processon.com/view/link/634695fb260d7157a7bc6ae0 3.Nacos2.x版本GRPC…

Visual Studio 2013 - 高亮设置括号匹配 (方括号)

Visual Studio 2013 - 高亮设置括号匹配 [方括号] 1. 高亮设置 括号匹配 (方括号)References 1. 高亮设置 括号匹配 (方括号) 工具 -> 选项… -> 环境 -> 字体和颜色 References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/

React - 实现菜单栏滚动

简介 本文将会基于react实现滚动菜单栏功能。 技术实现 实现效果 点击菜单&#xff0c;内容区域会自动滚动到对应卡片。内容区域滑动&#xff0c;指定菜单栏会被选中。 ScrollMenu.js import {useRef, useState} from "react"; import ./ScrollMenu.css;export co…

网络原理(5)——IP协议(网络层)

目录 一、IP协议报头介绍 1、4位版本 2、4位首部长度 3、8位服务器类型 4、16位总长度 5、16位标识位 6、3位标志位 7、13位偏移量 8、8位生存空间 9、8位协议 10、16位首部检验和 11、32位源IP地址 12、32位目的IP地址 二、IP协议如何管理地址&#xff1f; 1、动…

python 空间距离计算

目录 python 空间距离计算 已知两点&#xff0c;画三角形 批量矩阵计算 python 空间距离计算 要在空间中找到一个点&#xff0c;使其位于点 b 和 c 之间的连线上&#xff0c;并且与点 b 的距离等于点 a 到点 b 的距离的2倍。 import numpy as npif __name__ __main__:a …

链路聚合的应用场景

STP&#xff1a;聚合后计算 物理端口的速率叠加 链路聚合、端口聚合&#xff0c;链路捆绑 把多根链路逻辑捆绑在一起&#xff0c;当STP进行拓扑计算时此时会按照聚合后链路计算链路聚合物理链路速率的叠加最多可以用8个链路同时捆绑 1.提升带宽 2.增加网络的高可用性&#…

【计算机网络】基本概念

基本概念 IP 地址端口号协议协议分层封装分用客户端服务器请求和响应两台主机之间的网络通信流程 IP 地址 概念&#xff1a;IP 地址主要是用于唯一标识网络主机、其他网络设备&#xff08;如路由器&#xff09;的网络地址。简单来说&#xff0c;IP地址用来唯一定位主机。格式&…

ky10.aarch64安装Jenkins

参考地址&#xff1a;《安装部署 Jenkins》 前言 有war包和rpm两种安装方式&#xff0c;如果是长期使用更加推荐rpm的安装方式&#xff0c;可以更好的管理Jenkins&#xff1b; 我此次安装jenkins主要用于测试和简单的个人使用&#xff0c;所以选择更轻便的war安装。 1 下载J…

校招应聘流程讲解

在整个应聘流程中&#xff0c;记得保持积极的态度、认真准备面试&#xff0c;同时也要对自己的能力和经验有清晰的认识&#xff0c;这样才能在竞争激烈的校园招聘中脱颖而出&#xff0c;成功获得心仪的工作机会. 1. 校招资源获取 想要参加校招&#xff0c;首先需要获取校招资…

Mac上玩《赛博朋克2077》mac电脑怎么玩这个游戏

X用户crushovitz_b最近发现&#xff0c;在《赛博朋克2077》游戏主菜单页面&#xff0c;将鼠标停在版本号选项卡上面足够长时间&#xff0c;就会发现游戏当前的版本号由2.12变为了2.0.77&#xff0c;这是对游戏标题2077的致敬彩蛋。 《赛博朋克2077》的叙事总监兼续集副总监Pawe…

【漏洞复现】科立讯通信指挥调度平台editemedia.php sql注入漏洞

漏洞描述 在20240318之前的福建科立讯通信指挥调度平台中发现了一个漏洞。该漏洞被归类为关键级别,影响文件/api/client/editemedia.php的未知部分。通过操纵参数number/enterprise_uuid可导致SQL注入。攻击可能会远程发起。 免责声明 技术文章仅供参考,任何个人和组织使…

吴恩达机器学习笔记 二十七 决策树中连续值特征的选择 回归树

还是猫狗分类的案例&#xff0c;假如再增加一个特征weight&#xff0c;该值是一个连续的值&#xff0c;如何在决策树中使用该特征&#xff1f; 如下图所示&#xff0c;尝试不同的阈值&#xff0c;如 weight<9 , 此时左边有四个样本&#xff0c;都为猫&#xff0c;右边有六个…

【c++入门】引用,内联函数,auto

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本节我们来到c中一个重要的部分&#xff1a;引用 目录 1.引用的基本概念与用法1.1引用特性1.2使用场景1.3传值、传引用效率比较1.4引用做返回值1.5引用和指针的对…

企业微信可以更换公司主体吗?

企业微信变更主体有什么作用&#xff1f;当我们的企业因为各种原因需要注销或已经注销&#xff0c;或者运营变更等情况&#xff0c;企业微信无法继续使用原主体继续使用时&#xff0c;可以申请企业主体变更&#xff0c;变更为新的主体。企业微信变更主体的条件有哪些&#xff1…

搭建基于 Snowflake 的 CI/CD 最佳实践!

Snowflake 提供了可扩展的计算和存储资源&#xff0c;和基于 SQL 的界面 Snowsight&#xff0c;方便用户进行数据操作和分析。然而&#xff0c;如果用户想将自己的 CI/CD 流程与 Snowflake 集成时&#xff0c;会发现一些不便之处&#xff08;尤其相比其 SnowSight 优秀的查询能…

x-zse-96安卓端纯算,魔改AES还原

两天前发了一个x-zse-96的文章,当时遇到了点问题,只分析到了最后一个白盒AES函数里面,并且当时用dfa攻击还原出了秘钥,IV也确定了,但是加密结果不对,本来打算把下文鸽掉的,因为当时unidbg没跑起来,用frida去hook白盒AES中的每一行汇编有点麻烦,没有unidbg方便.后来小白大佬说un…

初识C++(一)

目录 一、什么是C 二、关键字&#xff1a; 三、命名空间 &#xff1a; 1. C语言存在的问题&#xff1a; 2. namespace关键字&#xff1a; 3. 注意点&#xff1a; 4.使用命名空间分为三种&#xff1a; 四、输入输出&#xff1a; 五、缺省函数&#xff1a; 1. 什么是缺省…

ARM实验 LED流水灯

.text .global _start _start: 使能GPIOE GPIOF的外设时钟 RCC_MP_AHB4ENSETR的第[4][5]设置为1即可使能GPIOE GPIOF时钟 LDR R0,0X50000A28 指定寄存器地址 LDR R1,[R0] 将寄存器原来的数值读取出来&#xff0c;保存到R1中 ORR R1,R1,#(0x3<<4) 将第4位设置为1 S…

【STM32嵌入式系统设计与开发】——6矩阵按键应用(4x4)

这里写目录标题 一、任务描述二、任务实施1、SingleKey工程文件夹创建2、函数编辑&#xff08;1&#xff09;主函数编辑&#xff08;2&#xff09;LED IO初始化函数(LED_Init())&#xff08;3&#xff09;开发板矩阵键盘IO初始化&#xff08;ExpKeyBordInit()&#xff09;&…

如何使用 Elasticsearch 作为向量数据库

在今天的文章中&#xff0c;我们将很快地通过 Docker 来快速地设置 Elasticsearch 及 Kibana&#xff0c;并设置 Elasticsearch 为向量搜索。 拉取 Docker 镜像 docker pull docker.elastic.co/elasticsearch/elasticsearch:8.12.2 docker pull docker.elastic.co/kibana/kiba…