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

LeetCode42.接雨水

 这道题呢可以按列来累加,就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度,我想到了这里然后就想第i列的水其实就是第i-1列和i+1列中最小的高度减去第i列的高度,但是其实并不是,比如示例中的第5列,他的告诉是0左右两边是1,但水是2,然后看题解了。

第i列的水其实与第i-1列和i+1列的水并没有关系,而是和第i列左边所有柱子中最高的和第i列右边所有柱子中最高的有关

当第i列左右两边的最高柱子中较矮的比第i列要高,那么第i列能装的水就是较矮的高度-第i列的高度。如果左右两边最高的柱子都比第i列的柱子矮的话,那么第i列能装的水就是0。所以算出每一列能装的水然后全部加起来就是能接到的雨水,以下的代码:

class Solution {public int trap(int[] height) {int n = height.length;int ans = 0;for(int i =1;i<n-1;i++){int leftMaxHeight =0;for(int j =i-1;j>=0;j--){if(height[j] > leftMaxHeight)leftMaxHeight=height[j];}int rightMaxHeight =0;for(int k =i+1;k<n;k++){if(height[k] > rightMaxHeight)rightMaxHeight=height[k];}int min = Math.min(rightMaxHeight, leftMaxHeight);ans+= min > height[i] ? min-height[i] : 0;}return ans;}
}

这个算法每次都要找出某一列左边的最高的柱子和右边的最高柱子,就多了一层循环,算法还可以优化,创建一个left_max数组和right_max数组,left_max[i]表示第i列左边的最高的柱子,right_max[i]同理。用动态规划的方法来填充这两个数组。

left_max[i] = Math,max(left_max[i-1] ,height[i-1]);就是说第i列左边最高的柱子是第i-1列左边的最高柱子第i-1列的高度的最大值,right_max[i]同理。以下是代码:

public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}

相关文章:

LeetCode42.接雨水

这道题呢可以按列来累加&#xff0c;就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度&#xff0c;我想到了这里然后就想第i列的水其实就是第i-1列和i1列中最小的高度减去第i列的高度&#xff0c;但是其实并不是&#xff0c;比如示例中的第5…...

优化时间流:区间调度问题的探索与解决

在浩如烟海的信息时代&#xff0c;时间的有效管理成为了一门不可或缺的艺术。无论是生活中的琐事&#xff0c;还是工作中的任务&#xff0c;时间都在无声地流逝&#xff0c;挑战着我们的智慧。正如时间在日常生活中具有的宝贵价值一样&#xff0c;在计算机科学领域&#xff0c;…...

【Python】强化学习:原理与Python实战

搞懂大模型的智能基因&#xff0c;RLHF系统设计关键问答 RLHF&#xff08;Reinforcement Learning with Human Feedback&#xff0c;人类反馈强化学习&#xff09;虽是热门概念&#xff0c;并非包治百病的万用仙丹。本问答探讨RLHF的适用范围、优缺点和可能遇到的问题&#xff…...

设计模式——合成复用原则

文章目录 合成复用原则设计原则核心思想合成案例聚合案例继承案例优缺点 合成复用原则 原则是尽量使用合成/聚合的方式&#xff0c;而不是使用继承 设计原则核心思想 找出应用中可能需要变化之处&#xff0c;把它们独立出来&#xff0c;不要和那些不需要变化的代码混在一起。…...

基于OpenCV实战(基础知识一)

目录 简介 1.计算机眼中的图像 2.图片的读取、显示与保存 3.视频的读取与显示 简介 OpenCV是一个流行的开源计算机视觉库&#xff0c;由英特尔公司发起发展。它提供了超过2500个优化算法和许多工具包&#xff0c;可用于灰度、彩色、深度、基于特征和运动跟踪等的图像处理和…...

如何高效的接入第三方接口

作为程序员的我们,经常会接到领导的安排,接入某某的接口,方面我们如何如何, 例如:领导在1号时给作为员工的你说,最近系统需要增加一个新的支付方式,一会和对方技术组建一个群,有什么问题,可以直接在群里说,最近还说,尽快接入,客户等着用,让你在5号前,完成接入工…...

docker pip下载依赖超时或失败问题解决

Docker容器使用pip安装Python库时超时&#xff0c;可能是由于多种原因。以下是一些建议和解决方法&#xff1a; 使用国内镜像源: 如果你位于中国&#xff0c;可以尝试更换到国内的镜像源。例如&#xff0c;可以使用阿里云、腾讯云、清华大学提供的镜像。 你可以在Dockerfile中添…...

python并发编程

一、程序提速的方法 二、python对并发编程的支持 多线程&#xff1a;threading&#xff0c;利用CPU和IO可以同时执行的原理&#xff0c;让CPU不会干巴巴等待IO完成&#xff1b;多进程&#xff1a;multiprocess&#xff0c;利用多核CPU的能力&#xff0c;真正的并行执行任务&am…...

【面试题】:前端怎么实现权限设计及遇到的bug

一.权限的概念 前端权限分为页面权限、按钮权限、API权限。 二.页面权限的实现过程 ①用户登录进去调用获取用户信息接口&#xff0c;后端会给我们返回一个权限标识符 ②在获取到数据之后,我们就要判断用户能访问到哪些页面,我们可以在vuex中permission模块中的action…...

Vue 2 插槽

可以先阅读组件基础-简单了解通过插槽分发内容。 一、插槽定义 插槽将子组件标签间的内容分发到子组件模板的<slot>标签位置。 如果没有<slot>标签&#xff0c;那么该内容将被丢弃。 二、编译作用域 内容在哪个作用域编译&#xff0c;就可以访问哪个作用域的数据…...

Spring 容器启动耗时统计

为了了解 Spring 为什么会启动那么久&#xff0c;于是看了看怎么统计一下加载 Bean 的耗时。 极简版 几行代码搞定。 import org.springframework.beans.BeansException; import org.springframework.beans.factory.config.BeanPostProcessor;import java.util.HashMap; imp…...

1. 优化算法学习

参考文献 1609&#xff1a;An overview of gradient descent optimization algorithms 从 SGD 到 Adam —— 深度学习优化算法概览(一) - 知乎 机器学习札记 - 知乎...

再获荣誉丨通付盾WAAP解决方案获“金鼎奖”优秀金融科技解决方案

今年四月&#xff0c;2023中国国际金融展在首钢会展中心成功落下帷幕。中国国际金融展作为金融开放创新成果的展示、交流、传播平台&#xff0c;历经多年发展,已成为展示中国金融发展成就、宣传金融改革成果、促进金融产业创新和推动金融信息化发展的有效平台。 “金鼎奖”评选…...

【腾讯云 TDSQL-C Serverless 产品测评】“橡皮筋“一样的数据库『MySQL高压篇』

【腾讯云 TDSQL-C Serverless 产品测评】"橡皮筋"一样的数据库 活动介绍服务一览何为TDSQL &#xff1f;Serverless 似曾相识&#xff1f; 降本增效&#xff0c;不再口号&#xff1f;动手环节 --- "压力"山大实验前瞻稍作简介资源扩缩范围&#xff08;CCU&…...

python http文件上传

server端代码 import os import cgi from http.server import SimpleHTTPRequestHandler, HTTPServer# 服务器地址和端口 host = 0.0.0.0 port = 8080# 处理文件上传的请求 class FileUploadHandler(SimpleHTTPRequestHandler):def do_POST(self):# 解析多部分表单数据form = …...

Android学习之路(9) Intent

Intent 是一个消息传递对象&#xff0c;您可以用来从其他应用组件请求操作。尽管 Intent 可以通过多种方式促进组件之间的通信&#xff0c;但其基本用例主要包括以下三个&#xff1a; 启动 Activity Activity 表示应用中的一个屏幕。通过将 Intent 传递给 startActivity()&…...

vue项目配置git提交规范

vue项目配置git提交规范 一、背景介绍二、husky、lint-staged、commitlint/cli1.husky2.lint-staged3.commitlint/cli 三、具体使用1.安装依赖2.运行初始化脚本3.在package.json中配置lint-staged4.根目录新增 commitlint.config.js 4.提交测试1.提示信息格式错误时2.eslint校验…...

影响交叉导轨运行速度的因素有哪些?

交叉导轨具有精度高&#xff0c;速度快&#xff0c;承载能力大、结构简单等特点&#xff0c;被广泛应用在固晶机、点胶设备、自动化设备、OA机器及其周边机器、测定器、印刷基板开孔机&#xff0c;精密机器&#xff0c;光学测试仪、光学工作台、操纵机构、X 射缐装置等的滑座部…...

List转Map

一、list转map Map<Long, User> maps userList.stream().collect(Collectors.toMap(User::getId,Function.identity())); 看来还是使用JDK 1.8方便一些。 二、另外&#xff0c;转换成map的时候&#xff0c;可能出现key一样的情况&#xff0c;如果不指定一个覆盖规则&…...

ES:一次分片设计问题导致的故障

### 现象&#xff1a; 1. 单节点CPU持续高 2.写入骤降 3.线程池队列积压&#xff0c;但没有reject 4.使用方没有记录日志 ### 排查 1.ES监控 只能看到相应的结果指标&#xff0c;无法反应出原因。 2.ES日志&#xff1a;大量日志打印相关异常&#xff08;routate等调用栈&a…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...

MeanFlow:何凯明新作,单步去噪图像生成新SOTA

1.简介 这篇文章介绍了一种名为MeanFlow的新型生成模型框架&#xff0c;旨在通过单步生成过程高效地将先验分布转换为数据分布。文章的核心创新在于引入了平均速度的概念&#xff0c;这一概念的引入使得模型能够通过单次函数评估完成从先验分布到数据分布的转换&#xff0c;显…...

Vue.js教学第二十一章:vue实战项目二,个人博客搭建

基于 Vue 的个人博客网站搭建 摘要: 随着前端技术的不断发展,Vue 作为一种轻量级、高效的前端框架,为个人博客网站的搭建提供了极大的便利。本文详细介绍了基于 Vue 搭建个人博客网站的全过程,包括项目背景、技术选型、项目架构设计、功能模块实现、性能优化与测试等方面。…...