C++ 优先算法——盛最多水的容器(双指针)

目录
题目:盛最多水的容器
1. 题目解析
2. 算法原理
3. 代码实现
题目:盛最多水的容器
1. 题目解析
题目截图:

如图所示:

水的高度一定是由较低的那条线的高度决定的:例1图中,是由7决定的,然后求出8和7它们对应的下标的之间的差,再进行相乘就得出体积。

题目的意思就是要我们找出一个数组中,两个下标对应的值,取它较小的那个值,并与两个下标之差的乘积,找出这个最大的乘积。
我们挑一组验证一下,题目给的结果是不是最大的

2. 算法原理
这道题有两种解法:
- 暴力枚举

- 利用单调性,使用双指针解决问题
这里解决用第二种方法,下来对这个方法进行解释

这样看出,取出的小部分向内 永远都是比第一次的v小,所以我们得出:当选区间最左、最右两个数,算出来一个容器之后,如果拿这个比较小的数向内枚举的话,发现容器是一直减小的,因此上述取的小部分对于4就不用考虑了。所以可以把这个单调性规律推广到整个数组。

然后算出来V1,发现1是较小的,然后就直接让left向后移动,不用再考虑1的向内枚举了


然后重复上面操作进行下去,直到两指针相遇。
我们可以总结一下:
- 向内枚举,w是肯定下降的。(w就是两个下标的差)。
- 若以两条垂线较低的那条向内枚举,那么h的变化情况:下降或不变。所以导致V是一直小于当前最大的V的,所以可以不用考虑。
- 所以谁指向的数较小,谁移动(指针向内移动)。
- 移动完后,继续算出一个容器V。
- 更新max。
- 再接着移动指针,重复上面操作。
- 指针相遇就结束。


所以这里用的还是双指针的方法,左右指针,向内移动,一起遍历整个数组,所以这个算法的时间复杂度是O(N)。
按照上述的逻辑,我们下面实现代码。
3. 代码实现
题目跳转:盛最多水的容器
//这里就是用的上面介绍的双指针法
class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while (left < right) {//用最小的那个当高,并与它们之间相减得出的距离结果相乘int V = min(height[left], height[right]) * (right - left);//每次都更新一下最大的体积ret = max(ret, V);// 移动指针 谁对应的值小谁移动// 注意left与right的移动方向if (height[left] < height[right]) {++left;} else {--right;}}return ret;}
};
提交结果:

制作不易,若有不足之处或出问题的地方,请各位大佬多多指教 ,感谢大家的阅读支持!!!

相关文章:
C++ 优先算法——盛最多水的容器(双指针)
目录 题目:盛最多水的容器 1. 题目解析 2. 算法原理 3. 代码实现 题目:盛最多水的容器 1. 题目解析 题目截图: 如图所示: 水的高度一定是由较低的那条线的高度决定的:例1图中,是由7决定的,然后求出…...
blender 小车建模 建模 学习笔记
一、学习blender视频教程链接 案例4:狂奔的小车_建模_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Bt4y1E7qn?p14&spm_id_from333.788.videopod.episodes&vd_sourced0ea58f1127eed138a4ba5421c577eb1 二、开始建模 (1)创…...
导出列表数据到Excel并下载
Java导出查询到的数据列表为Excel并下载 1.背景 工作中经常有需求,需要把列表的数据导出为Excel并下载。EasyExcel工具可以很好的实现这一需求。 2.实现流程 1.引入EasyExcel依赖包 <dependency><groupId>com.alibaba</groupId><artifactId…...
基于NVIDIA NIM平台实现盲人过马路的demo(一)
前言:利用NVIDIA NIM平台提供的大模型进行编辑,通过llama-3.2-90b-vision-instruct模型进行初步的图片检测 step1: 部署大模型到本地,引用所需要的库 import os import requests import base64 import cv2 import time from datetime import datetimestep2: 观看官方使用文…...
美格智能5G车规级通信模组:以连接+算力驱动智能化进阶
2023年3月,基于高通公司第二代骁龙汽车5G调制解调器及射频系统平台SA522M/SA525M,美格智能在德国纽伦堡嵌入式系统展上正式发布全新一代5G车规级C-V2X通信模组MA922系列,迅速引起行业和市场关注。随着5G高速网联逐步成为智能汽车标配…...
[MRCTF2020]PYWebsite1
如果输入的密钥是对的那么我们就直接跳转到flag.php页面 那么我们直接访问😎,他不带我们去我们自己去. 那就用XFF呗. 知识点: 定义:X-Forwarded-For是一个HTTP请求头字段,用于识别通过HTTP代理或负载均衡方式连接到W…...
无源元器件-磁珠选型参数总结
🏡《总目录》 目录 1,概述2,磁珠选型参数2.1,电学参数2.1.3,阻抗(Impedance)2.1.2,额定电流(Rated Current)2.1.3,直流电阻(DC Resistance)2.2,机械性能参数2.2.1,外观和尺寸(Appearance and Dimensions)2.2.2,粘接强度( Bonding Strength)2.2.3,弯曲强度…...
宝顶白芽,慢生活的味觉盛宴
在快节奏的生活中,人们愈发向往那种悠然自得、返璞归真的生活方式。白茶,以其独特的韵味和清雅的风格,成为了现代人追求心灵宁静与生活品质的象征。而在众多白茶之中,竹叶青茶业出品的宝顶白芽以其甘甜醇爽的特质,成为…...
已知三角形三边长求面积用仓颉语言作答
仓颉语言 https://cangjie-lang.cn/ linux和win和mac均有sdk,在本机deepinlinuxv23下载到本地解压缩到目录下设置环境变量 source envsetup.sh 比java方便太多了,java每次都是要自己搞很久,当然,打开看一下envsertup.sh,和我们…...
【JavaScript】匿名函数及回调函数总结
JavaScript 匿名函数 匿名函数没有显式的名称, 被视为一个函数表达式,可以在不需要额外命名的情况下进行定义和使用, 通常被用作回调函数, 即将函数作为参数传递给其他函数。 回调函数是在特定事件或条件发生时被调用的函数,回调函数通常用于异步编程中…...
HTML鼠标移动的波浪线动画——页面将会初始化一个Canvas元素,并使用JavaScript代码在Canvas上绘制响应鼠标移动的波浪线动画
代码如下 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Wave Animation</title><style&…...
树莓派开发相关知识八-其他传感器
1、蜂鸣器 #!/usr/bin/env python #coding:utf-8import RPi.GPIO as GPIO import time OUT5 def init():GPIO.setwarnings(False)GPIO.setmode(GPIO.BCM)GPIO.setup(OUT,GPIO.OUT)#蜂鸣器鸣叫函数 def beep(seconds):GPIO.output(OUT,GPIO.HIGH)time.sleep(seconds)GPIO.output…...
ComfyUI - ComfyUI 工作流中集成 SAM2 + GroundingDINO 处理图像与视频 教程
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/143359538 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 SAM2 与…...
STM32G4 双ADC模式之常规同步模式独立注入模式
目录 概述 1 认识双ADC模式 2 功能实现 2.1 原理介绍 2.2 实现方法 概述 本文主要介绍STM32G4 双ADC模式之常规同步模式&独立注入模式相关内容,包括ADC模块的功能介绍,实现框架结构,以及常规同步模式&独立注入模式ADC的转换的实…...
深入理解网络协议:OSPF、VLAN、NAT与ACL详解
OSPF工作过程与基础配置 一、OSPF的工作过程 OSPF(开放最短路径优先)是一个广泛使用的路由协议,它的工作过程可以总结为以下几个步骤: 启动与邻居发现 OSPF在配置完成后,会通过本地组播地址224.0.0.5发送HELLO包。HE…...
idea 配置tomcat 服务
选择tomcat的安装路径 选到bin的文件夹的上一层就行...
.net core 接口,动态接收各类型请求的参数
[HttpPost] public async Task<IActionResult> testpost([FromForm] object info) { //Postman工具测试结果: //FromBody,Postman的body只有rawjson时才进的来 //参数为空时,Body(form-data、x-www-form-urlencoded)解析到的数据也有所…...
关注!这些型号SSD有Windows蓝屏问题需要修复
近期,在闪迪官方有一个SSD FW升级提醒,主要是为了解决Windows 11 24H2系统蓝屏的问题: Fix问题:这些SSD的主机内存缓冲区(Host Memory Buffer,简称HMB)功能可能会导致系统出现蓝屏死机ÿ…...
go语言gin框架平滑关闭——思悟项目技术2
目录 前言 直接关闭的缺陷 平滑关闭的使用场景 例子 思悟项目: golang qq邮件发送验证码——思悟项目技术1 前言 平滑关闭(graceful shutdown)是指在停止服务时,能够让现有的连接、任务或者操作优雅地完成,而不是…...
K8S flannel网络模式对比
K8S flannel网络模式对比 VXLAN 模式Host-GW 模式如何查看 Flannel 的网络模式?如何修改 Flannel 的网络模式?如何修改flannel vxlan端口?Flannel 是一个 Kubernetes 中常用的网络插件,用于在集群中的节点之间提供网络连接。Flannel 提供了多种后端实现方式,vxlan 和 host…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
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、一个结构体实现多…...
