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

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

目录

题目:盛最多水的容器 

1. 题目解析

2. 算法原理

3. 代码实现


题目:盛最多水的容器 

1. 题目解析

题目截图:

如图所示:

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

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

我们挑一组验证一下,题目给的结果是不是最大的

2. 算法原理

这道题有两种解法:

  1. 暴力枚举
  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++ 优先算法——盛最多水的容器(双指针)

目录 题目&#xff1a;盛最多水的容器 1. 题目解析 2. 算法原理 3. 代码实现 题目&#xff1a;盛最多水的容器 1. 题目解析 题目截图: 如图所示&#xff1a; 水的高度一定是由较低的那条线的高度决定的&#xff1a;例1图中&#xff0c;是由7决定的&#xff0c;然后求出…...

blender 小车建模 建模 学习笔记

一、学习blender视频教程链接 案例4&#xff1a;狂奔的小车_建模_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Bt4y1E7qn?p14&spm_id_from333.788.videopod.episodes&vd_sourced0ea58f1127eed138a4ba5421c577eb1 二、开始建模 &#xff08;1&#xff09;创…...

导出列表数据到Excel并下载

Java导出查询到的数据列表为Excel并下载 1.背景 工作中经常有需求&#xff0c;需要把列表的数据导出为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月&#xff0c;基于高通公司第二代骁龙汽车5G调制解调器及射频系统平台SA522M/SA525M&#xff0c;美格智能在德国纽伦堡嵌入式系统展上正式发布全新一代5G车规级C-V2X通信模组MA922系列&#xff0c;迅速引起行业和市场关注。随着5G高速网联逐步成为智能汽车标配&#xf…...

[MRCTF2020]PYWebsite1

如果输入的密钥是对的那么我们就直接跳转到flag.php页面 那么我们直接访问&#x1f60e;&#xff0c;他不带我们去我们自己去. 那就用XFF呗. 知识点&#xff1a; 定义&#xff1a;X-Forwarded-For是一个HTTP请求头字段&#xff0c;用于识别通过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,弯曲强度…...

宝顶白芽,慢生活的味觉盛宴

在快节奏的生活中&#xff0c;人们愈发向往那种悠然自得、返璞归真的生活方式。白茶&#xff0c;以其独特的韵味和清雅的风格&#xff0c;成为了现代人追求心灵宁静与生活品质的象征。而在众多白茶之中&#xff0c;竹叶青茶业出品的宝顶白芽以其甘甜醇爽的特质&#xff0c;成为…...

已知三角形三边长求面积用仓颉语言作答

仓颉语言 https://cangjie-lang.cn/ linux和win和mac均有sdk&#xff0c;在本机deepinlinuxv23下载到本地解压缩到目录下设置环境变量 source envsetup.sh 比java方便太多了&#xff0c;java每次都是要自己搞很久&#xff0c;当然&#xff0c;打开看一下envsertup.sh,和我们…...

【JavaScript】匿名函数及回调函数总结

JavaScript 匿名函数 匿名函数没有显式的名称, 被视为一个函数表达式&#xff0c;可以在不需要额外命名的情况下进行定义和使用, 通常被用作回调函数, 即将函数作为参数传递给其他函数。 回调函数是在特定事件或条件发生时被调用的函数&#xff0c;回调函数通常用于异步编程中…...

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&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/143359538 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 SAM2 与…...

STM32G4 双ADC模式之常规同步模式独立注入模式

目录 概述 1 认识双ADC模式 2 功能实现 2.1 原理介绍 2.2 实现方法 概述 本文主要介绍STM32G4 双ADC模式之常规同步模式&独立注入模式相关内容&#xff0c;包括ADC模块的功能介绍&#xff0c;实现框架结构&#xff0c;以及常规同步模式&独立注入模式ADC的转换的实…...

深入理解网络协议:OSPF、VLAN、NAT与ACL详解

OSPF工作过程与基础配置 一、OSPF的工作过程 OSPF&#xff08;开放最短路径优先&#xff09;是一个广泛使用的路由协议&#xff0c;它的工作过程可以总结为以下几个步骤&#xff1a; 启动与邻居发现 OSPF在配置完成后&#xff0c;会通过本地组播地址224.0.0.5发送HELLO包。HE…...

idea 配置tomcat 服务

选择tomcat的安装路径 选到bin的文件夹的上一层就行...

.net core 接口,动态接收各类型请求的参数

[HttpPost] public async Task<IActionResult> testpost([FromForm] object info) { //Postman工具测试结果&#xff1a; //FromBody,Postman的body只有rawjson时才进的来 //参数为空时&#xff0c;Body(form-data、x-www-form-urlencoded)解析到的数据也有所…...

关注!这些型号SSD有Windows蓝屏问题需要修复

近期&#xff0c;在闪迪官方有一个SSD FW升级提醒&#xff0c;主要是为了解决Windows 11 24H2系统蓝屏的问题&#xff1a; Fix问题&#xff1a;这些SSD的主机内存缓冲区&#xff08;Host Memory Buffer&#xff0c;简称HMB&#xff09;功能可能会导致系统出现蓝屏死机&#xff…...

go语言gin框架平滑关闭——思悟项目技术2

目录 前言 直接关闭的缺陷 平滑关闭的使用场景 例子 思悟项目&#xff1a; golang qq邮件发送验证码——思悟项目技术1 前言 平滑关闭&#xff08;graceful shutdown&#xff09;是指在停止服务时&#xff0c;能够让现有的连接、任务或者操作优雅地完成&#xff0c;而不是…...

K8S flannel网络模式对比

K8S flannel网络模式对比 VXLAN 模式Host-GW 模式如何查看 Flannel 的网络模式?如何修改 Flannel 的网络模式?如何修改flannel vxlan端口?Flannel 是一个 Kubernetes 中常用的网络插件,用于在集群中的节点之间提供网络连接。Flannel 提供了多种后端实现方式,vxlan 和 host…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

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

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...