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

【算法|双指针系列No.4】leetcode11. 盛最多水的容器

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点解直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣算法分析
  • 3️⃣代码编写

1️⃣题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例1:

在这里插入图片描述

输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例2:

输入:height = [1,1]
输出:1

注意:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

2️⃣算法分析

通过不断地调整较短的边界来寻找可能的最大容量。因为容器的容量受限于较短的边界,所以选择移动较短的边界可以增加容器的高度,有可能得到更大的容量。通过不断缩小指针之间的宽度,直到指针重合,即可得到最大容量。

容器容量:v = s * h,由于我们这里不断移动两个“指针”,所以 s 是不断变小的,那么问题来了,我们要移动哪个指针呢(是向右移动左指针的,还是向左移动右指针呢?),我们要知道无论我们移动哪一个指针容器的 s 都是减小的,此时如果要使得容器容量增大,我们需要移动指针指向的值较小的那个指针。举个例子(1,9),我们此时就需要向右移动左指针了,因为我们只有移动左指针才有可能使得容器的容器容量变大(即通过增加h的方式)。
即:

if(height[l] < height[r]) l++;
else r--; 

3️⃣代码编写

class Solution {
public:int maxArea(vector<int>& height) {int l = 0,r = height.size() - 1,ret = 0;while(l < r){int v = (r - l) * min(height[l],height[r]);ret = max(v,ret);if(height[l] < height[r]) l++;else r--; }return ret;}
};

相关文章:

【算法|双指针系列No.4】leetcode11. 盛最多水的容器

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

数据结构全集介绍

以下列举了部分常见的数据结构&#xff1a; 数组&#xff08;Array&#xff09;&#xff1a;数组是一种线性数据结构&#xff0c;可以用来存储固定大小的数据集合。在数组中&#xff0c;每个元素都有一个对应的索引&#xff0c;可以通过索引直接访问和更新元素。数组的优点是访…...

力扣刷题-字符串-反转字符串

344 反转字符串 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间&#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中…...

【CCNP】第七章 动态路由协议-BGP

第一节 BGP的基本概念 BGP&#xff08;Border Gateway Protocol&#xff09;&#xff0c;边界网关协议 是运行在网络和网络之间的协议&#xff0c;是一款EGP&#xff08;外部网关协议&#xff09; BGP基于TCP协议工作&#xff0c;目的端口号179。源端口随机&#xff0c;由路由…...

java学习--day24(stream流)

文章目录 今天的内容1.Stream【难点】1.1获取流的对象1.2Stream流对象下面1.2.1count和forEach1.2.2filter方法1.2.3limit1.2.4map方法1.2.5skip1.2.6concat 1.3收集流 1.基于接口和抽象类的匿名内部类的写法 abstract class Person {public abstract void eat(); } public sta…...

Multi-Grade Deep Learning for Partial Differential Equations

论文阅读&#xff1a;Multi-Grade Deep Learning for Partial Differential Equations with Applications to the Burgers Equation Multi-Grade Deep Learning for Partial Differential Equations with Applications to the Burgers Equation符号定义偏微分方程定义FNN定义PI…...

Docker部署rustdesk

查看镜像版本 https://hub.docker.com/r/rustdesk/rustdesk-server/tags 拉取镜像 docker pull rustdesk/rustdesk-server:1.1.8-2创建挂载目录 mkdir -p /opt/rustdesk/{hbbr,hbbs}/root运行hbbs –nethost 仅适用于 Linux&#xff0c;它让 hbbs/hbbr 可以看到对方真实的…...

win1011安装MG-SOFT+MIB+Browser+v10b

文章目录 安装MG-SOFTSNMP服务配置安装MG-SOFT启动MIB-Browser以及错误解决MIB Browser使用 安装MG-SOFT win10和win11安装基本一样&#xff0c;所以参照下面的操作即可&#xff01; SNMP服务配置 打开设置&#xff0c;应用和功能&#xff0c;可选功能&#xff0c;选择添加功…...

PCL点云处理之Pcd文件读取、法线与曲率计算、多线程加速、属性字段合并 (二百零八)

PCL点云处理之Pcd文件读取、法线与曲率计算、多线程加速、属性字段合并(二百零八) 一、相关介绍二、算法实现1.代码一、相关介绍 (夜深人不静) 法线和曲率的计算是点云处理中常用的关键特征,PCL提供了特有的点类型PointNormal来记录这些信息,通过OMP多线程对相关的计算函…...

JavaEE-文件IO操作

构造方法 一般方法&#xff0c;有很多&#xff0c;我们以下只是列举几个经常使用的 注意在上述的操作过程中&#xff0c;无论是绝对路径下的这个文件还是相对路径下的这个文件&#xff0c;都是不存在的 Reader 使用 --> 文本文件 FileReader类所涉及到的一些方法 Fil…...

二蛋赠书四期:《Go编程进阶实战:开发命令行应用、HTTP应用和gRPC应用》

前言 大家好&#xff01;我是二蛋&#xff0c;一个热爱技术、乐于分享的工程师。在过去的几年里&#xff0c;我一直通过各种渠道与大家分享技术知识和经验。我深知&#xff0c;每一位技术人员都对自己的技能提升和职业发展有着热切的期待。因此&#xff0c;我非常感激大家一直…...

MySQL数据库基本操作-DQL-排序查询

介绍 如果我们需要对读取的数据进行排序&#xff0c;我们就可以使用 MySQL 的 order by 子句来设定你想按哪个字段哪种方式来进行排序&#xff0c;再返回搜索结果。 语法 select 字段名1&#xff0c;字段名2&#xff0c;…… from 表名 order by 字段名1 [asc|desc]&#xf…...

这是一篇测试文章

这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章这是一篇测试文章…...

Ubuntu plt画图 新罗马字体网格marker刻度朝内

* 字体文件&#xff1a;坚果云下code包&#xff0c;新罗马字体 参考链接&#xff1a;Linux下Matplotlib画图New Times Roman字体设置 - 知乎 * 刻度朝内 plt.rcParams[font.sans-serif] [Times New Roman]plt.rcParams[xtick.direction]in#设置x轴刻度向内plt.rcParams[ytic…...

flutter布局中的一些细节

前言 记录flutter使用中遇到的一些细节和坑&#xff0c;希望能帮助到大家 Column中不能直接嵌套ListView, &#xff08;需要指定ListView的高度或者加上shrinkWrap: true属性&#xff09;需要限制button的大小&#xff0c;可以在外部嵌套一个Container或SizedBox来限制在List…...

论文解析——AMD EPYC和Ryzen处理器系列的开创性的chiplet技术和设计

ISCA 2021 摘要 本文详细解释了推动AMD使用chiplet技术的挑战&#xff0c;产品开发的技术方案&#xff0c;以及如何将chiplet技术从单处理器扩展到多个产品系列。 正文 这些年在将SoC划分成多个die方面有一系列研究&#xff0c;MCM的概念也在不断更新&#xff0c;AMD吸收了…...

第二证券:汽车产业链股活跃,恒勃股份、博俊科技“20cm”涨停

轿车产业链股9日盘中走势活跃&#xff0c;截至发稿&#xff0c;恒勃股份、博俊科技“20cm”涨停&#xff0c;德迈仕涨超17%&#xff0c;上声电子涨超14%&#xff0c;川环科技涨超10%&#xff0c;圣龙股份、科华控股、沪光股份、上海沿浦、日盈电子、赛力斯等均涨停。 工作方面…...

孙帅Spring源码

【视频来源于&#xff1a;B站up主孙帅suns Spring源码视频】【微信号&#xff1a;suns45】...

jenkins工具系列 —— 插件 使用Changelog获取commit记录

文章目录 安装changelog插件重启jenkins配置 ChangelogExecute shell 使用 changelog邮件中html格式也可以使用构建测试&#xff08;查看构建项 -> 控制台输出&#xff09; 安装changelog插件 插件文件可通过 V 获取 点击 左侧的 Manage Jenkins —> Plugins ——> …...

【JavaScript】浅拷贝与深拷贝

引言 浅拷贝、深拷贝是对引用类型而言的。 引用类型的变量对应一个栈区地址&#xff0c;这个栈区地址处存储的值是存放的真正的数据的堆区地址。 基本数据类型的变量也对应一个栈区地址&#xff0c;但是该地址存储的是其真正的值。 let a b发生了什么&#xff1f; let obj…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...