hot100:07接雨水
题目链接:
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
算法思想:
这里采取的是暴力解法和双指针的解法,但是这个题目还有其他的两种解法(单调栈和动态规划,同学可以自行了解)
首先,在说算法思想之前,我们需要搞懂题目的意思,什么样情况属于可以接到雨水,如何相加,下面看一幅图来了解一下:

对于i下标对应的元素来说,它需要先找到左右两边的最大高度(要保证两边的高度都得大于i对应的高度),找到之后选择两边高度的较小值减去自己对应的高度就是所接到的雨水的量
暴力解法:
遍历整个数组,统计每个元素接到的雨水量进行相加(注意数组的遍历可以从1下标开始,因为0下标肯定是接不到雨水的)
//暴力解法public int trap(int[] height) {int n = height.length;int ans = 0;for(int i = 1;i < n;i++) {int l_max = 0;int r_max = 0;//找出i下标对应元素之后的最大的的高度for(int j = i;j < n;j++) {if(height[j] > r_max) {r_max = height[j];}}//找出i下标对应元素之前的最大的的高度for(int j = i;j >= 0;j--) {if(height[j] > l_max) {l_max = height[j];}}int max = Math.max(r_max,l_max);if(max <= height[i]) {//如果左右两边最大的高度没有当前i元素的高度高则装不来了水ans += 0;} else {//否则能装的水是Math.min(r_max,l_max) - height[i];ans += Math.min(r_max,l_max) - height[i];}}return ans;}
双指针解法:
使用两个指针left和right分别指向数组的第一个元素和最后一个元素,判断的终止条件是left=right,定义两个变量leftMax和rightMax分别表示遍历到元素高度的最大值,如果height[left]<height[right]则以左边为基准,接到的雨水量为leftMax-height[left],然后更新left,left++,反之接到的雨水量就是rightMax-height[right],right--
//双指针解法public int trap(int[] height) {int left = 0;int right = height.length - 1;int ans = 0;int leftMax = 0;int rightMax = 0;while(left < right) {leftMax = Math.max(leftMax,height[left]);rightMax = Math.max(rightMax,height[right]);if(height[left] < height[right]) {ans += leftMax - height[left];left++;} else {ans += rightMax - height[right];right--;}}return ans;}
相关文章:
hot100:07接雨水
题目链接: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 算法思想: 这里采取的是暴力解法和双指针的解法,但是这个题目还有其他的两种解法(单调栈和动态规划,同学可以自行了解ÿ…...
Docker安装MySQL教程分享(附MySQL基础入门教程)
docker安装MySQL Docker可以通过以下命令来安装MySQL容器: 首先确保已经在计算机上安装了Docker。如果没有安装,请根据操作系统的不同进行相应的安装。 打开终端或命令提示符,并运行以下命令拉取最新版本的MySQL镜像: docker pu…...
麒麟V10挂载iso,配置yum源
本文介绍yum 如何挂载本地镜像源 1) 拷贝镜像到本地 2) 执行以下命令: # mount -o loop 镜像路径及镜像名字 /mnt(或 media) 挂载前 挂载后 3) 进入/etc/yum.repos.d(yum.repos.d 是一个目录,该目录是分析 RPM 软件…...
《Linux C编程实战》笔记:信号的捕捉和处理
Linux系统中对信号的处理主要由signal和sigaction函数来完成,另外还会介绍一个函数pause,它可以用来响应任何信号,不过不做任何处理 signal函数 #include <signal.h> void (*signal(int signum, void (*handler)(int)))(int);可以分解…...
python算法与数据结构---单调栈与实践
单调栈 单调栈是一个栈,里面的元素的大小按照它们所在栈的位置,满足一定的单调性; 性质: 单调递减栈能找到左边第一个比当前元素大的元素;单调递增栈能找到左边第一个比当前元素小的元素; 应用场景 一般用…...
文心一言使用分享
ChatGPT 和文心一言哪个更好用? 一个直接可以用,一个还需要借助一些工具,还有可能账号会消失…… 没有可比性。 通用大模型用于特定功能的时候需要一些引导技巧。 import math import time def calculate_coordinate(c, d, e, f, g, h,…...
【C++干货铺】C++11新特性——lambda表达式 | 包装器
个人主页点击直达:小白不是程序媛 C系列专栏:C干货铺 代码仓库:Gitee 目录 C98中的排序 lambda表达式 lambda表达式语法 表达式中的各部分说明 lambda表达式的使用 基本的使用 [var]值传递捕捉变量var 编辑 [&var]引用传递捕…...
在 EggJS 中实现 Redis 上锁
配置环境 下载 Redis Windows 访问 https://github.com/microsoftarchive/redis/releases 选择版本进行下载 - 勾选 [配置到环境变量] - 无脑下一步并安装 命令行执行:redis-cli -v 查看已安装的 Redis 版本,能成功查看就表示安装成功啦~ Mac brew i…...
Unity-场景
创建场景 创建新的场景后: 文件 -> 生成设置 -> Build中的场景 -> 将项目中需要使用的场景拖进去 SceneTest public class SceneTest : MonoBehaviour {// Start is called before the first frame updatevoid Start(){// 两个类: 场景类、场…...
MATLAB R2023b for Mac 中文
MATLAB R2023b 是 MathWorks 发布的最新版本的 MATLAB,适用于进行算法开发、数据可视化、数据分析以及数值计算等任务的工程师和科学家。它包含了一系列新增功能和改进,如改进了数据导入工具,增加了对数据帧和表格对象的支持,增强…...
01 MyBatisPlus快速入门
1. MyBatis-Plus快速入门 版本 3.5.31并非另起炉灶 , 而是MyBatis的增强 , 使用之前依然要导入MyBatis的依赖 , 且之前MyBatis的所有功能依然可以使用.局限性是仅限于单表操作, 对于多表仍需要手写 项目结构: 先导入依赖,比之前多了一个mybatis-plus…...
HarmonyOS 应用开发入门
HarmonyOS 应用开发入门 前言 DevEco Studio Release版本为:DevEco Studio 3.1.1。 Compile SDK Release版本为:3.1.0(API 9)。 构建方式为 HVigor,而非 Gradle。 最新版本已不再支持 (”Java、JavaScrip…...
【机器学习300问】9、梯度下降是用来干嘛的?
当你和我一样对自己问出这个问题后,分析一下!其实我首先得知道梯度下降是什么,也就它的定义。其次我得了解它具体用在什么地方,也就是使用场景。最后才是这个问题,梯度下降有什么用?怎么用? 所以…...
第13章 1 进程和线程
文章目录 程序和进程的概念 p173函数式创建子进程Process类常用的属性和方法1 p175Process类中常用的属性和方法2 p176继承式创建子进程 p177进程池的使用 p178并发和并行 p179进程之间数据是否共享 p180队列的基本使用 p180使用队列实现进程之间的通信 p182函数式创建线程 p18…...
什么是中间件?
文章目录 为什么需要中间件?中间件生态漫谈数据库中间件读写分离分库分表引进数据库中间件MyCat 服务端代理模式ShardingJDBC 客户端代理模式 总结 IT 系统从单体应用逐渐向分布式架构演变,高并发、高可用、高性能、分布式等话题变得异常火热,…...
汽车售后服务客户满意度调查报告
本文由群狼调研(长沙旅行社满意度调查)出品,欢迎转载,请注明出处。汽车售后服务客户满意度调查报告通常包括以下内容: 1.调研概况:介绍调研的目的、背景和范围,包括调研的时间、地点和样本规模等…...
初始RabbitMQ(入门篇)
消息队列(MQ) 本质上就是一个队列,一个先进先出的队列,队列中存放的内容是message(消息),是一种跨进程的通信机制,用于上下游传递消息, 为什么使用MQ: 削峰填谷: MQ可以很好的做一个缓冲机制,例如在一个系统中有A和B两个应用,A是接收用户的请求的,然后A调用B进行处理. 这时…...
JVM:Java类加载机制
Java类加载机制的全过程: 加载、验证、准备、初始化和卸载这五个阶段的顺序是确定的,类型的加载过程必须按照这种顺序按部就班地开始,而解析阶段则不一定:它在某些情况下可以在初始化阶段之后再开始, 这是为了支持Java…...
要经历痛苦,才能在赚钱路上觉醒!
新手赚钱,一个秘诀就够了! 黎明前的黑暗实际是最漫长的,就如同开发进度99%到100%这个过程尤其漫长。赚钱的路上起初就是黑暗,不断地摸索最终才能走出迷雾,真正的迎接朝阳。如果有一段路程,十来公里的路线&a…...
LeetCode 第381场周赛个人题解
目录 100191. 输入单词需要的最少按键次数 I 原题链接 题目描述 思路分析 AC代码 100188. 按距离统计房屋对数目 I 原题链接 题目描述 思路分析 AC代码 100192. 输入单词需要的最少按键次数 II 原题链接 题目描述 思路分析 AC代码 100213. 按距离统计房屋对数目…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
python打卡第47天
昨天代码中注意力热图的部分顺移至今天 知识点回顾: 热力图 作业:对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图,展示模…...
Springboot 高校报修与互助平台小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,高校报修与互助平台小程序被用户普遍使用,为…...
IP选择注意事项
IP选择注意事项 MTP、FTP、EFUSE、EMEMORY选择时,需要考虑以下参数,然后确定后选择IP。 容量工作电压范围温度范围擦除、烧写速度/耗时读取所有bit的时间待机功耗擦写、烧写功耗面积所需要的mask layer...
android计算器代码
本次作业要求实现一个计算器应用的基础框架。以下是布局文件的核心代码: <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"andr…...
成工fpga(知识星球号)——精品来袭
(如需要相关的工程文件请关注知识星球:成工fpga,https://t.zsxq.com/DMeqH,关注即送200GB学习资料,链接已置顶!) 《孩子都能学会的FPGA》系列是成工完成的第一个系列,也有一年多的时…...
