当前位置: 首页 > 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…...

手游刚开服就被攻击怎么办?如何防御DDoS?

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

大话软工笔记—需求分析概述

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

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...