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;}
};

提交结果:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/730.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

SQL-lab靶场less1-4

说明&#xff1a;部分内容来源于网络&#xff0c;如有侵权联系删除 前情提要&#xff1a;搭建sql-lab本地靶场的时候发现一些致命的报错&#xff1a; 这个程序只能在php 5.x上运行&#xff0c;在php 7及更高版本上&#xff0c;函数“mysql_query”和一些相关函数被删除&#xf…

Golang | Leetcode Golang题解之第535题TinyURL的加密与解密

题目&#xff1a; 题解&#xff1a; import "math/rand"type Codec map[int]stringfunc Constructor() Codec {return Codec{} }func (c Codec) encode(longUrl string) string {for {key : rand.Int()if c[key] "" {c[key] longUrlreturn "http:/…

使用 Elasticsearch 进行语义搜索

Elasticsearch 是一款功能强大的开源搜索引擎&#xff0c;可用于全文搜索、分析和数据可视化。传统上&#xff0c;Elasticsearch 以其执行基于关键字/词汇的搜索的能力而闻名&#xff0c;其中文档基于精确或部分关键字匹配进行匹配。然而&#xff0c;Elasticsearch 已经发展到支…

计算机毕业设计Python+大模型新闻自动分类 新闻舆情预测 新闻语料情感分析 新闻推荐系统 朴素贝叶斯分类算法 机器学习 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

【097】基于SpringBoot+Vue实现的个人社区博客管理系统

系统介绍 演示视频 小白博客2.0&#xff08;SpringbootVue)源码数据库讲解视频设计文档 基于SpringBootVue实现的小白博客2.0系统设计了超级管理员、系统观察者、用户三种角色&#xff0c;超级管理员可对用户授权&#xff0c;具体实现的功能如下 文章采用了比较火的Markdown编…

LM Head weights;ChatGPT-3词汇量:175,000;llama7b 词汇量,词嵌入维度:4096

目录 LM Head weights ChatGPT-3词汇量:175,000 llama7b 词汇量 词汇量:32000 max_position_embeddings: 4096 LM Head weights ChatGPT-3词汇量:175,000 ChatGPT-4 确切的词向量种类数量公开信息。但可以根据一些语言模型的相关知识进行推测分析。 一般来说,语言模…

ArcGIS005:ArcMap常用操作101-150例动图演示

摘要&#xff1a;本文涵盖了GIS软件操作的多方面内容&#xff0c;包括地图文档的新建、打开、保存及版本兼容性处理&#xff1b;错误与警告的查阅及帮助文档的使用技巧&#xff1b;地图打印比例尺的调整与地图信息的完善&#xff1b;图层操作的撤销与恢复&#xff0c;界面元素的…

Chrome和夸克谁更护眼

在当今数字化时代&#xff0c;我们每天长时间面对电脑和手机屏幕&#xff0c;眼睛的健康问题变得越来越重要。浏览器作为我们日常使用频率极高的工具&#xff0c;其护眼功能的优劣直接影响到我们的视觉舒适度。本文将对Chrome和夸克两款主流浏览器进行对比&#xff0c;探讨它们…

WPF+MVVM案例实战(十二)- 3D数字翻牌计时实现

文章目录 1、运行效果2、功能实现1、文件创建2、控件代码实现3、控件引用与菜单实现1.引用用户控件2.按钮菜单3、计时器界面实现4、源代码获取1、运行效果 3D数字翻牌计时 2、功能实现 1、文件创建 打开项目 Wpf_Examples ,在用户控件 UserControlLib 中创建 NumberFoldi…

一、计算机网络概述,《计算机网络(自顶向下方法 第7版,James F.Kurose,Keith W.Ross)》

文章目录 [toc]零、前言一、什么是Internet1.1 从具体构成角度1.2 什么是协议1.3 从服务角度1.4 网络结构 二、网络边缘2.1 通讯模式2.2 采用网络设施的面向连接服务2.3 采用基础设施的无连接服务 三、网络核心3.1 认识网络核心3.2 网络核心&#xff1a;电路交换3.2.1 基本原理…

闯关leetcode——234. Palindrome Linked List

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/palindrome-linked-list/description/ 内容 Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Example 1: Input: head [1,2,2,1] Output: tru…

K8S自建企业私有云方案 单台起配 NVMe全闪存储性能

作为老牌存储硬件厂商&#xff0c;Infortrend这回开了一把大的。在一套设备系统里&#xff0c;将计算节点、存储与Kubernetes结合&#xff0c;打造出EonStor KS IEC&#xff08;Infortrend企业云&#xff09;&#xff0c;将硬件与软件、前端与后端、上层与底层统一融合在一套系…

Rust 力扣 - 73. 矩阵置零

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 我们使用两个变量记录矩阵初始状态的第一行与第一列是否存在0 然后我们遍历矩阵&#xff08;跳过第一行与第一列&#xff09;&#xff0c;如果矩阵中元素为0则将该元素映射到矩阵第一行与矩阵第一列的位置置为0…

6款IntelliJ IDEA插件,让Spring和Java开发如虎添翼

文章目录 1、SonarLint2、JRebel for IntelliJ3、SwaggerHub插件4、Lombok插件5、RestfulTool插件6、 Json2Pojo插件7、结论 对于任何Spring Boot开发者来说&#xff0c;两个首要的目标是最大限度地提高工作效率和确保高质量代码。IntelliJ IDEA 是目前最广泛使用的集成开发环境…

Node.js:ES6 模块化 Promise

Node.js&#xff1a;ES6 模块化 & Promise ES6 模块化默认导入导出按需导入导出 Promise构造状态thencacheallraceasyncawait ES6 模块化 在Node.js中&#xff0c;遵循的是CommonJS的模块化规范&#xff0c;使用require方法导入模块&#xff0c;使用moudule.exports导出模…

利用STM32控制3D打印机时优化打印精度的教学

引言 在3D打印的过程中&#xff0c;打印精度直接影响到最终产品的质量与性能。STM32作为一种强大的微控制器&#xff0c;广泛应用于3D打印机的控制系统中。本文将介绍如何利用STM32控制3D打印机&#xff0c;并提供优化打印精度的具体方法&#xff0c;包括环境准备、代码示例、常…

基于 MATLAB的混沌序列图像加密算法的研究

一、设计目的及意义 3 二、研究现状 3 三、设计内容 3 四、开发环境 3 五、分析设计 3 1、设计要求 3 2、设计原理 3 3、涉及到的程序代码 ........................................... 4 4、主要思想 6 六、 果及分析 6 1、运行示例 6 2、 果 估 8 七、参考文献 9 八 、 研 究…

了解密钥推导函数KDF-HMAC-SHA-256

引言 在现代密码学中&#xff0c;密钥推导函数&#xff08;KDF&#xff0c;Key Derivation Functions&#xff09;扮演着至关重要的角色。它们允许从主密钥或密码生成一个或多个固定长度的密钥&#xff0c;用于各种加密操作。KDF的设计目标是确保从同一主密钥生成的多个密钥在统…

什么是数字签名技术?

信息安全五要素 名称说明机密性机密性是指网络信息不泄露给非授权的用户、实体或程序&#xff0c;能够防止非授权者获取信息完整性完整性是指网络信息或系统未经授权不能进行更改的特性可用性可用性是指合法许可的用户能够及时获取网络信息或服务的特性可控性可控性是指可以控…

clickhouse运维篇(三):生产环境一键生成配置并快速部署ck集群

前提条件&#xff1a;先了解集群搭建流程是什么样&#xff0c;需要改哪些配置&#xff0c;有哪些环境&#xff0c;这个文章目的是简化部署。 clickhouse运维篇&#xff08;一&#xff09;&#xff1a;docker-compose 快速部署clickhouse集群 clickhouse运维篇&#xff08;二&am…