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

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接雨水

题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 算法思想&#xff1a; 这里采取的是暴力解法和双指针的解法&#xff0c;但是这个题目还有其他的两种解法&#xff08;单调栈和动态规划&#xff0c;同学可以自行了解&#xff…...

Docker安装MySQL教程分享(附MySQL基础入门教程)

docker安装MySQL Docker可以通过以下命令来安装MySQL容器&#xff1a; 首先确保已经在计算机上安装了Docker。如果没有安装&#xff0c;请根据操作系统的不同进行相应的安装。 打开终端或命令提示符&#xff0c;并运行以下命令拉取最新版本的MySQL镜像&#xff1a; docker pu…...

麒麟V10挂载iso,配置yum源

本文介绍yum 如何挂载本地镜像源 1) 拷贝镜像到本地 2) 执行以下命令&#xff1a; # mount -o loop 镜像路径及镜像名字 /mnt&#xff08;或 media&#xff09; 挂载前 挂载后 3) 进入/etc/yum.repos.d&#xff08;yum.repos.d 是一个目录&#xff0c;该目录是分析 RPM 软件…...

《Linux C编程实战》笔记:信号的捕捉和处理

Linux系统中对信号的处理主要由signal和sigaction函数来完成&#xff0c;另外还会介绍一个函数pause&#xff0c;它可以用来响应任何信号&#xff0c;不过不做任何处理 signal函数 #include <signal.h> void (*signal(int signum, void (*handler)(int)))(int);可以分解…...

python算法与数据结构---单调栈与实践

单调栈 单调栈是一个栈&#xff0c;里面的元素的大小按照它们所在栈的位置&#xff0c;满足一定的单调性&#xff1b; 性质&#xff1a; 单调递减栈能找到左边第一个比当前元素大的元素&#xff1b;单调递增栈能找到左边第一个比当前元素小的元素&#xff1b; 应用场景 一般用…...

文心一言使用分享

ChatGPT 和文心一言哪个更好用&#xff1f; 一个直接可以用&#xff0c;一个还需要借助一些工具&#xff0c;还有可能账号会消失…… 没有可比性。 通用大模型用于特定功能的时候需要一些引导技巧。 import math import time def calculate_coordinate(c, d, e, f, g, h,…...

【C++干货铺】C++11新特性——lambda表达式 | 包装器

个人主页点击直达&#xff1a;小白不是程序媛 C系列专栏&#xff1a;C干货铺 代码仓库&#xff1a;Gitee 目录 C98中的排序 lambda表达式 lambda表达式语法 表达式中的各部分说明 lambda表达式的使用 基本的使用 [var]值传递捕捉变量var ​编辑 [&var]引用传递捕…...

在 EggJS 中实现 Redis 上锁

配置环境 下载 Redis Windows 访问 https://github.com/microsoftarchive/redis/releases 选择版本进行下载 - 勾选 [配置到环境变量] - 无脑下一步并安装 命令行执行&#xff1a;redis-cli -v 查看已安装的 Redis 版本&#xff0c;能成功查看就表示安装成功啦~ Mac brew i…...

Unity-场景

创建场景 创建新的场景后&#xff1a; 文件 -> 生成设置 -> Build中的场景 -> 将项目中需要使用的场景拖进去 SceneTest public class SceneTest : MonoBehaviour {// Start is called before the first frame updatevoid Start(){// 两个类&#xff1a; 场景类、场…...

MATLAB R2023b for Mac 中文

MATLAB R2023b 是 MathWorks 发布的最新版本的 MATLAB&#xff0c;适用于进行算法开发、数据可视化、数据分析以及数值计算等任务的工程师和科学家。它包含了一系列新增功能和改进&#xff0c;如改进了数据导入工具&#xff0c;增加了对数据帧和表格对象的支持&#xff0c;增强…...

01 MyBatisPlus快速入门

1. MyBatis-Plus快速入门 版本 3.5.31并非另起炉灶 , 而是MyBatis的增强 , 使用之前依然要导入MyBatis的依赖 , 且之前MyBatis的所有功能依然可以使用.局限性是仅限于单表操作, 对于多表仍需要手写 项目结构&#xff1a; 先导入依赖&#xff0c;比之前多了一个mybatis-plus…...

HarmonyOS 应用开发入门

HarmonyOS 应用开发入门 前言 DevEco Studio Release版本为&#xff1a;DevEco Studio 3.1.1。 Compile SDK Release版本为&#xff1a;3.1.0&#xff08;API 9&#xff09;。 构建方式为 HVigor&#xff0c;而非 Gradle。 最新版本已不再支持 &#xff08;”Java、JavaScrip…...

【机器学习300问】9、梯度下降是用来干嘛的?

当你和我一样对自己问出这个问题后&#xff0c;分析一下&#xff01;其实我首先得知道梯度下降是什么&#xff0c;也就它的定义。其次我得了解它具体用在什么地方&#xff0c;也就是使用场景。最后才是这个问题&#xff0c;梯度下降有什么用&#xff1f;怎么用&#xff1f; 所以…...

第13章 1 进程和线程

文章目录 程序和进程的概念 p173函数式创建子进程Process类常用的属性和方法1 p175Process类中常用的属性和方法2 p176继承式创建子进程 p177进程池的使用 p178并发和并行 p179进程之间数据是否共享 p180队列的基本使用 p180使用队列实现进程之间的通信 p182函数式创建线程 p18…...

什么是中间件?

文章目录 为什么需要中间件&#xff1f;中间件生态漫谈数据库中间件读写分离分库分表引进数据库中间件MyCat 服务端代理模式ShardingJDBC 客户端代理模式 总结 IT 系统从单体应用逐渐向分布式架构演变&#xff0c;高并发、高可用、高性能、分布式等话题变得异常火热&#xff0c…...

汽车售后服务客户满意度调查报告

本文由群狼调研&#xff08;长沙旅行社满意度调查&#xff09;出品&#xff0c;欢迎转载&#xff0c;请注明出处。汽车售后服务客户满意度调查报告通常包括以下内容&#xff1a; 1.调研概况&#xff1a;介绍调研的目的、背景和范围&#xff0c;包括调研的时间、地点和样本规模等…...

初始RabbitMQ(入门篇)

消息队列(MQ) 本质上就是一个队列,一个先进先出的队列,队列中存放的内容是message(消息),是一种跨进程的通信机制,用于上下游传递消息, 为什么使用MQ: 削峰填谷: MQ可以很好的做一个缓冲机制,例如在一个系统中有A和B两个应用,A是接收用户的请求的,然后A调用B进行处理. 这时…...

JVM:Java类加载机制

Java类加载机制的全过程&#xff1a; 加载、验证、准备、初始化和卸载这五个阶段的顺序是确定的&#xff0c;类型的加载过程必须按照这种顺序按部就班地开始&#xff0c;而解析阶段则不一定&#xff1a;它在某些情况下可以在初始化阶段之后再开始&#xff0c; 这是为了支持Java…...

要经历痛苦,才能在赚钱路上觉醒!

新手赚钱&#xff0c;一个秘诀就够了&#xff01; 黎明前的黑暗实际是最漫长的&#xff0c;就如同开发进度99%到100%这个过程尤其漫长。赚钱的路上起初就是黑暗&#xff0c;不断地摸索最终才能走出迷雾&#xff0c;真正的迎接朝阳。如果有一段路程&#xff0c;十来公里的路线&a…...

LeetCode 第381场周赛个人题解

目录 100191. 输入单词需要的最少按键次数 I 原题链接 题目描述 思路分析 AC代码 100188. 按距离统计房屋对数目 I 原题链接 题目描述 思路分析 AC代码 100192. 输入单词需要的最少按键次数 II 原题链接 题目描述 思路分析 AC代码 100213. 按距离统计房屋对数目…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...