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…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...