leetcode--盛最多水的容器,接雨水
11.盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1] 输出:1提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
题解:
随便选择两条线,那么容纳的水量就是这块蓝色的面积。接着,看右边这条更短的线,它和中间的线构成容器的话,我们可以分类讨论一下:
(1)如果中间的线比它短,那么容纳的水宽度变短,高度变小,则这一部分的面积肯定比蓝色部分的面积小
(2)如果中间的线一样长,或者比它长,那么容纳水的高度不变,宽度变小,则这一部分的面积仍然比蓝色部分的面积小
因此中间的任何线都无法与它构成容量更大的容器了。换句话说,如果要找到一个容量比蓝色区域部分更大的容器,那么肯定不会包含这条线(如 ,右边这条红色的线),所以可以直接去掉,在剩下的线中继续去找
既然这样,那我们可以初始化两个指针,left-0,right=n-1,哪条线短就移动哪条,如果一样长,移动两个的任意一个即可。在移动之前,先把所围成的面积算出来,如果比答案大,就更新答案
时间复杂度为O(N)
空间复杂度为O(1)
class Solution {
public:int maxArea(vector<int>& height) {int ans=0;int n=height.size();int area;//存储最大水量//相向双指针的用法int left=0;int right=n-1;while(left<right){area=min(height[right],height[left])*(right-left);ans=max(area,ans);if(height[left]<height[right])left+=1;elseright-=1;}return ans;}
};
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 * 104
0 <= height[i] <= 105
题解:
对于接雨水, 对于某一竖列i看它能接多少水, 就看它左侧的最大墙壁高度以及右侧的最大墙壁高度。
如果所有左侧墙壁最大高度或者右侧墙壁最大高度都低于当前竖列i的情况下, 这一竖列不可能接到水, 因为会从它左侧或者右侧流出,只有当左侧出现有高于当前墙壁以及右侧也高于当前墙壁时,才可以接到水。
竖列i接到的水=左右侧最低的那面墙-当前i墙壁的高度,然后对每一个竖列墙壁都这么计算
class Solution {
public:int trap(vector<int>& height) {int ans=0;int left=0;int right=height.size()-1;int pre_max=0;//前缀和int suf_max=0;//后缀和while(left<right){pre_max=max(pre_max,height[left]);suf_max=max(suf_max,height[right]);ans+=pre_max<suf_max?pre_max-height[left++]:suf_max-height[right--];}return ans;}
};
相关文章:
leetcode--盛最多水的容器,接雨水
11.盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明:你不…...
AlexNet网络搭建
AlexNet网络模型搭建 环境准备 首先在某个盘符下创建一个文件夹,就叫AlexNet吧,用来存放源代码。 然后新建一个python文件,就叫plot.py吧,往里面写入以下代码,用于下载数据集: # FashionMNIST里面包含了…...
常用第三方库:sqflite数据库应用
常用第三方库:sqflite数据库应用 一、基础概念 1.1 什么是sqflite? sqflite是Flutter官方推荐的SQLite数据库插件,它提供了在Flutter应用中使用SQLite数据库的能力。SQLite是一个轻量级的、嵌入式的关系型数据库,特别适合移动应…...
【论文阅读】-周总结-第5周
1. 【论文阅读24】并行 TCN-LSTM 风电预测模型(2024-02) 链接 论文信息: Liu S, Xu T, Du X, et al. A hybrid deep learning model based on parallel architecture TCN-LSTM with Savitzky-Golay filter for wind power prediction. Ener…...
深入理解 JavaScript 的 typeof 运算符:返回的数据类型
JavaScript 的 typeof 运算符是开发中用于检测值类型的基础工具。虽然看似简单,但其行为存在需要开发者理解的微妙细节。本文将解析 typeof 返回的数据类型,探讨边界案例,并分享类型检查的最佳实践。 typeof 会返回哪些类型? typ…...
前端零基础入门到上班:【Day8】JavaScript 基础语法入门
前端零基础入门到上班:【Day8】JavaScript 基础语法入门(超全!!!) 一、JavaScript 简介二、引入 JavaScript 的三种方式三、变量与常量(var、let、const)3.1 var (传统方式ÿ…...
ppt流程图怎么?ppt流程图模板大全
ppt流程图怎么?ppt流程图剪头模板,ppt流程图模板大全: ppt流程图_模板素材_PPT模板_ppt素材_免抠图片_AiPPTer...
makefile总结
Makefile 学习视频:1、野火的基础入门篇-第32讲 Makefile三要素_哔哩哔哩_bilibili 2、b站视频04 一个稍复杂的Makefile_哔哩哔哩_bilibili 学习资料:第2个视频对应的Make/make.md 无限十三年/CPP - 码云 - 开源中国 ch0_Makefile简介 Makefile是什…...
MIME 类型是个什么东西?
MIME 类型(Multipurpose Internet Mail Extensions)即多用途互联网邮件扩展类型,它是一种标准,用于表示文档、文件或字节流的性质和格式。 最初设计用于电子邮件系统,后来被广泛应用于网页、HTTP 协议等领域࿰…...
javaWeb开发---前后端开发全景图解(基础梳理 + 技术体系)
在现代互联网开发中,前端与后端的分工协作非常重要。本文结合实际架构图,全面梳理前端技术栈、后端技术栈以及服务器端整体流程,帮助初学者建立清晰的整体认知。 一、整体架构概览 系统整体划分为三个主要部分: B端(…...
spring-rabbit的CachingConnectionFactory默认参数导致消费者Channel数量暴增问题解决
文章目录 1.前言2.解决2.1消费监听方法中关闭channel2.2 配置设置两个参数 3.总结 1.前言 由于之前写了一个好用的rabbitmq-spring-boot-start启动器,后面在生产实践之后反馈消费者连接的Channel数量过多,一个消费者的Channel数量可以达到好几百…...
线上JVM调优与全栈性能优化 - Java架构师面试实战
线上JVM调优与全栈性能优化 - Java架构师面试实战 本文通过一场互联网大厂的Java架构师面试,深入探讨了线上JVM调优、OOM定位、死锁定位、内存和CPU调优、线程池调优、数据库调优、缓存调优、网络调优、微服务调优及分布式调优等关键领域。 第一轮提问 面试官&am…...
【KWDB创作者计划】_企业级多模数据库实战:用KWDB实现时序+关系数据毫秒级融合(附代码、性能优化与架构图)
一、技术背景与行业痛点 1.1 多模数据融合挑战 场景痛点: 工业物联网设备每秒产生百万级传感器数据(时序数据)。需关联设备档案(关系数据)生成设备健康报告,传统方案需多数据库跳转,延迟>5…...
“八股训练营”学习总结
在参加为期 40 天的八股训练营的这段时间里,我收获满满,不仅在知识技能上得到了提升,更在学习习惯和自我认知方面有了很大的进步。 在知识层面,训练营涵盖了网络、数据库、缓存以及python测试开发等多方面的知识点。 网络方面&a…...
java工具类
LocalDateTime LocalDateTime可以获取当前时间: LocalDateTime now LocalDateTime.now(); 同时他也可以获取指定时间: LocalDateTime dateTime LocalDateTime.of(2023, 5, 15, 10, 30) 若我们时间值超出了我们的实际情况值,我们将会出现…...
「OC」源码学习——alloc与init的实现
「OC」源码学习——alloc与init的实现 前言 费劲千辛万苦终于项目给写完了,进入下一个阶段,源码的学习 alloc的调用顺序 我们在main函数之中打上断点,先运行 再在alloc之中的各个函数之中打上断点,在关键步骤上打上断点&#…...
AOSP Android14 Launcher3——动画核心类QuickstepTransitionManager详解
Launcher3中,有一个类在跟桌面相关的各种动画中扮演着非常关键的角色,这个类就是QuickstepTransitionManager。 QuickstepTransitionManager在aosp中的路径为:aosp/packages/apps/Launcher3/quickstep/src/com/android/launcher3/QuickstepT…...
STM32:看门狗
独立看门狗 简介 独立看门狗(IWDG)由独立的低速时钟(LSI)驱动,即便主时钟发生故障,它依然能够正常工作。其主要作用是在程序出现异常时,通过复位来保障系统的稳定性。独立看门狗的喂狗操作相对…...
第十三步:vue
Vue 1、上手 1、安装 使用命令:npm create vuelatestvue文件后缀为.vueconst app createApp(App):初始化根组件app.mount("#app"):挂载根组件到页面 2、文件 script标签:编写jstemplate标签:编写htmls…...
《代码整洁之道》第8章 边界 - 笔记
甚至是你团队里其他组写的你无法随意修改的代码。 这些外部代码是你的**“边界”。它们可能会升级、可能会有 Bug、可能会有反人类的设计、甚至你将来可能想换一个类似的库或服务。如果你的应用代码直接且紧密地依赖**这些外部代码的具体类、方法、异常等细节,那么…...
【CF】Day45——Codeforces Round 1021 (Div. 2) BC
阅读理解。。。不过挺有意思( B. Sasha and the Apartment Purchase 题目: 思路: 看了半天没看懂... 题目叽里咕噜一大堆,说白了就是让我们在一个 可删除k个数 的 数组 中选 一些点 且 这些点的f(x) 是此时 删完了k个数之后的数组…...
《代码整洁之道》第5章 格式 - 笔记
你应该选择一套管理代码格式的简单规则。如果是团队,应该选择一套团队一致同意采用的简单格式规则。 最重要的原则:一致性(Consistency)! 没有完美的格式规范,但有统一的规范。 整个团队(或者…...
通过示例学习:连续 XOR
通过示例学习:连续 XOR 如果我们想在 PyTorch 中构建神经网络,可以使用 (with) 指定所有参数(权重矩阵、偏差向量),让 PyTorch 计算梯度,然后调整参数。但是,如果我们有很…...
加密算法 AES、RSA、MD5、SM2 的对比分析与案例(AI)
加密算法 AES、RSA、MD5、SM2 的对比分析 一、相同点 密码学基础 均为现代密码学核心算法,用于保障数据安全。数据处理 均涉及数据转换(加密、签名、哈希等)。密钥依赖 AES、RSA、SM2 依赖密钥(对称或非对称&#x…...
基于STM32、HAL库的MAX31865模数转换器ADC驱动程序设计
一、简介: MAX31865是一款高精度的铂电阻温度检测器(RTD)至数字转换器,具有以下特点: 支持2线、3线或4线RTD配置 15位ADC分辨率 可编程RTD和基准电阻 内置故障检测(开路、短路等) SPI接口通信 工作电压:3.0V至3.6V 二、硬件接口: STM32L4XX <--> MAX31865 PA5(SCK…...
Laravel5.7的一些用法
1、事件需要运行 php artisan queue:work 2、数据库对象关联 1对1 hasOne 1对多 hasMany 1依赖多 belongsTo 多依赖多 belongsToMany 3、 关联查询 with 关联统计 withCount 统计时指定字段名。 如: withCount([cardHolderOrders as order_count]); 4、 // 一次查询&…...
Vue3 + OpenLayers 开发教程 (六)WebGL渲染优化
1. WebGL 渲染优化 1.1 WebGL 渲染器配置 创建 src/utils/webgl.ts: import { Map } from ol; import { WebGLPointsLayer } from ol/layer; import { Vector as VectorSource } from ol/source; import { Style, Circle, Fill, Stroke } from ol/style;// 创建 …...
【C++】C++11新特性(一)
文章目录 列表初始化initializer_list左值引用和右值引用 列表初始化 在 C98 中可以使用{}对数组或者结构体元素进行统一的列表初始值设定 struct Point {int _x;int _y; }; int main() {int array1[] { 1, 2, 3, 4, 5 };int array2[5] { 0 };Point p { 1, 2 };return 0; …...
【网络原理】 网络编程套接字
文章目录 一、网络编程基础1. 为什么需要网络编程?2. 什么是网络编程3 .网络编程中的基本概念发送端和接收端请求和响应客户端和服务端 4. 常见的客户端服务端模型 二、Socket套接字1. 概念2.分类3. Java数据报套接字通信模型4.Java流套接字通信模型 三、UDP数据报套…...
每天五分钟深度学习框架pytorch:使用visdom绘制损失函数图像
visdom的安装 pip install visdom如果安装失败 pip install --upgrade visdom开启visdom python -m visdom.server nohup python -m visdom.server后台启动然后就会出现,下面的页面,我们可以使用下面的链接打开visdom页面 Visdom中有两个重要概念: env环境。不同环境的可…...
【MySQL专栏】MySQL数据库表的内外连接
文章目录 1、表的内连接(1)内连接的语法格式①显示SMITH的名字和部门名称 2、外连接(1)左外连接左外连接的语法格式通过实例演示: (2)右外连接右外连接的语法格式通过实例演示 1、表的内连接 什…...
-信息革命-
信息革命-马歇尔麦克卢汉(MARSHALL McLUHAN),1964年 随着大系统的加速崩溃,作为塑造经济生活和收入分配的一个因素,系统性的强 制将会式微。很快,在社会机构的组织中,效率将会比权力的分配更加重…...
Charles 抓包入门教程
一、什么是 Charles? Charles 是一款功能强大的抓包工具,可以拦截、查看、分析电脑和手机上的 HTTP/HTTPS 网络请求。常用于: 查看网页或App发送的请求和返回的数据调试接口、分析问题模拟网络环境(断网、慢速网络)修…...
深度学习新趋势:利用MLP取代卷积层——S2-MLPv2模型解析
深度学习新趋势:利用MLP取代卷积层——S2-MLPv2模型解析 近年来,深度学习领域不断涌现出新的技术革新,而其中最引人注目的趋势之一就是用多层感知机(MLP)替代传统的卷积层。这种转变不仅带来了计算效率的提升…...
【玩转 JS 函数式编程_016】DIY 实战:巧用延续传递风格(CPS)重构倒计时特效逻辑
文章目录 巧用延续传递风格(CPS)重构倒计时特效逻辑1 起因2 换一种思路3 填坑之旅4 复盘与小结 写在前面 都说念念不忘,必有回响。写过的文章也好,看过的视频也罢,其实只要用心积累,不必刻意去死记硬背&…...
虚函数表的设计和多态的实现
虚表指针 类直接定义虚函数:编译器自动在对象头部插入 vptr。 继承含虚函数的父类:子类复用父类的 vptr,不会创建新的vptr 单继承(子类继承一个含虚函数的父类) 1.创建新的虚函数表 2.沿用父类的虚表指针ÿ…...
中国科学院大学计算机考研历年初试分数线分析以及计算机所考的科目有哪些?
以下是对中国科学院大学计算机考研历年初试分数线分析以及计算机所考科目的介绍: 历年初试分数线分析 • 2024 年 :计算机应用技术专业(专业代码 081203)和计算机技术专业(专业代码 085404)的复试分数线为…...
Simulink与C的联合仿真调试
背景 simulink的Matlab Function,默认采用double类型的数据,无法定制int或者single类型的数据;Simulink中的Matlab Function直接调用.m文件中的函数(该函数中对数据类型有single或者int的定义),该函数中的…...
DeepSeek 多头潜在注意力(Multi-Head Latent Attention, MLA)技术
1. 核心原理 多头潜在注意力(MLA)是Transformer架构的扩展技术,通过潜在空间投影和多注意力头并行计算增强模型对长序列和复杂特征的建模能力。 1.1 关键技术点 潜在空间压缩 将原始高维注意力矩阵投影到低维潜在空间,降低计算复…...
C# 类(Class)教程
在现代面向对象编程中,**类(Class)**是最基础、最重要的概念之一。通过学习类,我们可以理解怎样定义自己的数据类型,封装数据与行为,构建复杂的软件体系结构。本文将详细介绍C#中的类,从基础定义…...
Kubernetes学习笔记-环境变量的使用
如果项目需要一些灵活配置,减少硬编码或者避免敏感信息的暴露,可以考虑使用Kubernetes Pod下的容器的环境变量。 Pod容器设置环境变量的方式: 可以通过Deployment配置文件的env字段来设置环境变量 value env:- name: ACTIVE_PROFILEvalue: …...
git提交规范记录,常见的提交类型及模板、示例
Git提交规范是一种约定俗成的提交信息编写标准,旨在使代码仓库的提交历史更加清晰、可读和有组织。以下是常见的Git提交类型及其对应的提交模板: 提交信息的基本结构 一个标准的Git提交信息通常包含以下三个主要部分: Header:描…...
关于指针和指针算术
第一次读C primer plus 第六版时,关于指针的语法一些名词没有用心去理解,再读的时候,讲到指针算术这个词时,感觉之前读像是漏了很关键的点,这次读,写下关于指针算术的思考。 有漏了的感觉是,在…...
el-input限制输入只能是数字 限制input只能输入数字
方法一: 通过设置type属性:type“number”,这种方式一般会影响样式,不建议使用,如下图: <el-input type"number" v-model"aaa"></el-input>方法二: 通过绑定值…...
Pydantic:校验器(@validator)、模型嵌套、模型继承
📚 1. 校验器(validator) Pydantic 允许你自定义字段验证逻辑。用 validator 装饰器可以在字段赋值时自动进行检查或修改。 例子: from pydantic import BaseModel, validatorclass User(BaseModel):name: strage: intvalidato…...
343. 整数拆分
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2输出: 1解释: 2 1 1, 1 1 1。 示例 2: 输入: 10输出: 36解释: 10 3 3 4, 3 3 4 36。说明: 你可以假设 n 不小于 2…...
前端面试 js
作用域链 内存管理 垃圾回收器 引用计数 默认栈里面会有一次引用 问题:循环引用,会产生内存泄漏 标记清除 垃圾回收期会定期从根开始遍历,找到有引用的对象 闭包 内存泄漏 this的指向 默认绑定 独立调用的this都是window function foo()…...
Linux CentOS 安装Python 3.8.0
在 CentOS 上升级 Python 3.6.8 到 3.8.0,可以按照以下步骤操作: 1. 安装依赖 sudo yum groupinstall -y "Development Tools" sudo yum install -y openssl-devel bzip2-devel libffi-devel zlib-devel wget 如果遇到报错“File "/bin…...
EXCEL常用函数公式和VBA汇总第二篇
系列文章目录 文章目录 系列文章目录前言一、excel公式应用1.rand函数2.rand函数随机排序3.rand函数提取数据4.correl函数5.SUBSTITUTE函数6.MAX组合函数7.分析下班时间8.柏拉图自动排序 总结 前言 一、excel公式应用 1.rand函数 用excel生成1-5的随机数字,其中对…...
Python 基础核心知识
1. Python 特点 简洁易读:代码简洁,强制缩进(取代花括号)。动态类型:变量无需声明类型(如 x 10)。跨平台:支持 Windows、Linux、macOS。丰富的库:如 NumPy(…...