leetcode第十一题:盛最多水的容器

给定一个长度为 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

步骤 1:问题性质分析

这个问题属于双指针算法的经典应用场景,通常用来寻找数组中符合条件的最大值。在此问题中,我们需要找到一对垂线使得它们与 x 轴构成的容器可以容纳最多的水量。

  • 输入条件

    • 整数数组 height,长度为 n,表示 n 条垂直线的高度。
    • 每一条垂线的坐标为 (i, 0)(i, height[i])i 是该垂线的索引。
  • 输出条件

    • 返回两条垂线间的容器可以容纳的最大水量。
  • 约束条件

    • 2 <= n <= 10^5,保证数组至少有两条线。
    • 0 <= height[i] <= 10^4,高度可以为0,表示没有高度的线。
  • 问题的几何本质

    • 两条垂线的 x 坐标距离越大,容器的宽度越大。
    • 两条垂线中较短的一条决定了容器的高度,容器的容量等于 min(height[left], height[right]) * (right - left),即两条线中较短的高度乘以它们的横向距离。

步骤 2:算法设计思路

我们可以使用双指针法来解决这个问题。双指针法能够在O(n) 时间复杂度内找到结果,符合题目对大规模数据的要求。

1. 初始化双指针

将两个指针分别放在数组的两端,一个指向最左边的线,另一个指向最右边的线。这样可以从最大可能的宽度开始计算。

2. 计算当前容器的容量

每次根据当前两条线的高度和它们的距离计算当前容器的容量。容量公式为:

3. 移动指针

为了尽可能找到更大的容器,我们要移动指针。移动规则是:

  • 总是移动高度较小的那条线的指针。这是因为容器的高度是由较短的那条线决定的,移动较小的高度有机会遇到更高的线从而增加容量。
4. 终止条件

当左指针与右指针相遇时,循环终止。此时我们已经检查过了所有可能的容器,最大值也已找到。

5. 时间复杂度

双指针从两端逐步向中间移动,整个过程最多遍历数组一次,因此时间复杂度为 O(n)

6. 空间复杂度

由于使用了常数空间的双指针,空间复杂度为 O(1)

步骤 4:算法的启发

  • 双指针法的应用:通过左右夹逼的方式,我们有效减少了计算的复杂度,这是双指针法处理连续子序列问题的一个典型应用。

  • 效率的提升:相比暴力解法(遍历所有的可能组合,时间复杂度为 O(n²)),双指针法的时间复杂度为 O(n),这是一个显著的优化。在处理大规模数据时,这种优化尤为重要。

  • 数据规模处理能力:通过这一问题的解决,我们能看出,在大规模数据集上,优化算法的时间复杂度至关重要。很多问题可以通过空间换时间或者特定的策略,如双指针法,达到更高的效率。

步骤 5:实际应用场景

双指针法的思想可以广泛应用于需要在一个连续空间中寻找最优解的场景。一个实际应用的例子是物流仓储的优化

  • 物流场景示例:假设在一个仓库中,有一系列货架,每个货架的宽度固定,但高度不同。要在两个货架之间摆放最多的货物,要求货物的高度不能超过较矮的货架高度,且摆放的区域宽度是两个货架之间的距离。在这种情况下,我们可以用双指针法来找到能摆放最多货物的两组货架。
实现方法:
  • 使用货架的编号作为数组的索引,货架的高度作为数组的元素。通过双指针法找到能够容纳最多货物的两组货架,帮助优化仓库的布局,提高货物摆放效率。通过这种方式,仓库管理系统可以自动推荐货物的最佳存放位置,提高物流的吞吐量。

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

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

相关文章

简单题101. 对称二叉树 (python)20240922

问题描述&#xff1a; python: # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right rightclass Solution(object):def isSymm…

Windows内网穿透远程桌面操作指南

1、登录NatCross官网https://www.natcross.com 账密登录或手机验证码登录。 2、点击左侧场景映射&#xff0c;选择【3389远程桌面】点击添加。 3、检查本地ip&#xff1a;127.0.0.1为本机&#xff0c;本地端口默认&#xff1a;3389&#xff0c;点击保存&#xff0c;系统生产成外…

【LeetCode】每日一题 2024_9_22 找到小镇的法官(模拟)

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 题目&#xff1a;找到小镇的法官 代码与解题思路 func findJudge(n int, trust [][]int) int {// 我当时的思路就是&#xff1a;每个人&#xff08;除了小镇法官&#xff09;都信任这位小镇法官。// 直接…

黑马头条day2-2 freemaker minio

其实就是freemaker生成一个静态页面 然后存储到minio上 返回一个链接在表里 最后直接通过url访问minio里边的动态页面 freemaker和minio 就是一个展示一个存储 下边这个弹幕感觉说的很清楚 遇到的问题 1 依赖报错 引不到依赖 一直没找到问题出在哪里 明明在pom文件里边引入了…

Docker配置代理解决pull超时问题

操作系统: CentOS Linux 8 Docker版本: 26.1.3 前置&#xff1a;你需拥有&#x1f431; 1. 配置 proxy.conf 1.1 创建配置文件目录 创建 docker.service.d&#xff0c;进入到 docker.service.d 中打开 proxy.conf (没有文件打开会自动创建)。 注意&#xff1a;每个人的路径可…

GRE隧道协议学习笔记

使用场景 分布在不同地理位置的总公司和分公司怎么通过网络连接起来&#xff1f; 可以使用ISP网络连接。在豆包中可以看到如下回答通俗的讲就是运营商收费提供网络服务&#xff0c;有个人的有企业的&#xff0c;企业的很贵 为什么要使用GRE隧道 当然你也可以用其他隧道协议…

C++_22_异常

文章目录 异常概念&#xff1a;**抛出异常&#xff1a;**关键字&#xff1a; **捕获异常&#xff1a;****栈解旋&#xff1a;****异常的接口声明&#xff1a;****异常对象的生命周期&#xff1a;**1 传递异常对象【不使用】2 传递异常对象指针【不使用】3 传递异常对象引用【**…

论 JAVA 集合框架中 接口与类的关系

前言 这是笔者在学习过程中的一篇"备忘录",其目的是能用最EZ最粗鄙的语言口述出 JAVA集合框架中 所有类与接口的关系 本人在不断地学习中,总会混淆集合框架中的类和接口,以及它们的作用关系,虽然不影响我的使用,但是我也不想一直糊涂下去,故而趁知识还没混淆之际,赶…

【练习16】求最小公倍数

链接&#xff1a;求最小公倍数_牛客题霸_牛客网 (nowcoder.com) 题目分析&#xff1a; 要求最小公倍数&#xff0c;要先用辗转相除法求最大公约数。假如有两个数a、b&#xff1a; 最小公倍数a*b / a和b的最大公约数 最大公约数 &#xff08;b, a % b&#xff09;&#xff0c;直…

Redis数据结构之zset

一.zset有序集合 它和集合唯一不同的就是&#xff0c;有序集合中的每一个元素都有一个唯一对应的浮点类型的分数与之关联着&#xff0c;是的有序集合中的元素可以维护有序性。 但是这个有序不适用下标作为排序的依据&#xff0c;而是使用这个分数。就好像排行榜一样&#xff…

Spark MLlib实践指南:从大数据推荐系统到客户流失预测的全流程建模

问题一 背景&#xff1a; 本题目基于用户数据&#xff0c;将据数据切分为训练集和验证集&#xff0c;供建模使用。训练集与测试集切分比例为8:2。 数据说明&#xff1a; capter5_2ml.csv中每列数据分别为userId , movieId , rating , timestamp。 数据&#xff1a; capte…

jboss

一。CVE-2015-7501 1.POC&#xff0c;访问地址 192.168.10.193:8080/invoker/JMXInvokerServlet 返回如下&#xff0c;说明接⼝开放&#xff0c;此接⼝存在反序列化漏洞 2.下载 ysoserial ⼯具进⾏漏洞利⽤ https://github.com/frohoff/ysoserial 将反弹shell进⾏base64编码…

828华为云征文 | 使用Flexus X实例搭建Dubbo-Admin服务

一、Flexus X实例简介 华为云推出的Flexus云服务&#xff0c;作为专为中小企业及开发者设计的新一代云服务产品&#xff0c;以其开箱即用、体验卓越及高性价比而著称。其中的Flexus云服务器X实例&#xff0c;更是针对柔性算力需求量身打造&#xff0c;能够智能适应业务负载变化…

msvcp100.dll丢失怎样修复,总共有6种修复方法

在现代的数字化生活中&#xff0c;电脑已经成为我们工作、学习和娱乐的重要工具。然而&#xff0c;由于各种原因&#xff0c;电脑可能会出现各种问题&#xff0c;其中最常见的就是一些系统文件丢失或损坏。最近&#xff0c;有用户反映他们的电脑出现了“msvcp100.dll丢失”的问…

QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第七期]

QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第七期] 第七期介绍&#xff1a;事件订阅之WebSocket方式 目录 QQ频道机器人零基础开发详解(基于QQ官方机器人文档)[第七期]第七期介绍&#xff1a;事件订阅之WebSocket方式 WebSocket方式通用数据结构 Payload长连接维护 O…

LLMs之LCM:《MemLong: Memory-Augmented Retrieval for Long Text Modeling》翻译与解读

LLMs之LCM&#xff1a;《MemLong: Memory-Augmented Retrieval for Long Text Modeling》翻译与解读 导读&#xff1a;MemLong 是一种新颖高效的解决 LLM 长文本处理难题的方法&#xff0c;它通过外部检索器获取历史信息&#xff0c;并将其与模型的内部检索过程相结合&#xff…

Linux C高级day3

一、思维导图 二、练习 #!/bin/bash mkdir ~/dir mkdir ~/dir/dir1 mkdir ~/dir/dir2 cp -r * ~/dir/dir1/ cp -r *.sh ~/dir/dir2/ cd ~/dir/dir2/ tar -cvJf dir2.tar.xz dir2 mv dir2.tar.xz ~/dir/dir1/ cd ~/dir/dir1 tar -xvJf dir2.tar.xz #!/bin/bash head -5 /etc/gr…

高版本JMX Console未授权

1.环境搭建 cd vulhub-master/jboss/CVE-2017-12149 docker-compose up -d 2.访问漏洞地址 nullhttp://47.121.211.205:8080/jmx-console/ 3.远程下载war包 输入远程war包的地址 http://47.121.211.205/shell.war 4.访问上传文件并进行连接 访问上传文件 使用工具进行连…

Jboss 靶场攻略

CVE-2015-7501 步骤一&#xff1a;环境搭建 cd vulhub/jboss/JMXInvokerServlet-deserialization docker-compose up -d docker ps 步骤二&#xff1a;POC&#xff0c;访问地址 http://192.168.10.190:8080/invoker/JMXInvokerServlet 返回如下&#xff0c;说明接⼝开放&…

【Linux进程】进程退出

目录 前言 1. 进程退出的几种情况 2. 进程常见的退出方式 3. 退出码与错误码 4. 进程异常 5. exit与_exit 6. 进程等待 wait与waitpid 获取子进程status 非阻塞等待 前言 进程执行结束退出&#xff0c;就必然需要进行资源回收&#xff0c;子进程由父进程回收&#xff0c…