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

双指针系列第 8 篇:盛水最多的容器。几句话讲明白!

在这里插入图片描述

Leetcode 题目链接

思路

取首尾双指针和水量如下所示,设高度函数为 h ( i ) h(i) h(i),在下图中 h ( l ) < h ( r ) h(l) < h(r) h(l)<h(r)
Screenshot 2024-07-03 at 6.30.09 PM.png

观察以 l l l 为左边界所能构成的其他水量,与矮的右边界搭配结果如下。
Screenshot 2024-07-03 at 6.30.13 PM.png

与高的右边界搭配结果如下。
Screenshot 2024-07-03 at 6.30.15 PM.png

我们可以发现水量都会变小,即无法通过当前 l l l 获得更大的水量,可在记录水量后舍弃 l l l,使其右移。

如果初始 h ( l ) > h ( r ) h(l) > h(r) h(l)>h(r), 则镜像处理,令 r r r左移。

如果初始 h ( l ) = h ( r ) h(l) = h(r) h(l)=h(r),任意移动均可。

此后循环分析这个过程并移动指针即可。

严谨证明

假设初始 h ( l ) < h ( r ) h(l) < h(r) h(l)<h(r),当前可容纳的水量记为 c = ( r − l ) × h ( l ) c = (r - l) \times h(l) c=(rl)×h(l)

∀ i ∈ ( l , r ) \forall i \in (l, r) i(l,r) i i i l l l 作为边界对应的可容纳水量记为 c ′ = ( i − l ) × m i n { h ( i ) , h ( l ) } c' = (i - l) \times min\{h(i),\ h(l)\} c=(il)×min{h(i), h(l)},其中:

  • i − l < r − l i - l < r - l il<rl
  • m i n { h ( i ) , h ( l ) } ≤ h ( l ) min\{h(i),\ h(l)\} \leq h(l) min{h(i), h(l)}h(l)

c ′ < c c' < c c<c,可在记录水量后舍弃 l l l,令 l l l 右移,因为无法通过 l l l 获得更大的水量。

余下分析同上。

代码

仅提供 java 代码。

class Solution {public int maxArea(int[] height) {int l = 0;int r = height.length - 1;int maxCap = 0; // 待返回的最大水量while (l < r) {int cap = (r - l) * Math.min(height[l], height[r]);maxCap = Math.max(maxCap, cap);if (height[l] < height[r]) {l++;} else {r--;}}return maxCap;}
}

复杂度

时间: Θ ( n ) \Theta(n) Θ(n)
空间: Θ ( 1 ) \Theta(1) Θ(1)

推广

以下皆为个人所著,兼顾了职场面试和本硕阶段的学术考试。

  • 附个人题解的双指针题单
  • 图论入门
  • 图论进阶

点赞关注不迷路,祝各位早日上岸,飞黄腾达!

相关文章:

双指针系列第 8 篇:盛水最多的容器。几句话讲明白!

Leetcode 题目链接 思路 取首尾双指针和水量如下所示&#xff0c;设高度函数为 h ( i ) h(i) h(i)&#xff0c;在下图中 h ( l ) < h ( r ) h(l) < h(r) h(l)<h(r)。 观察以 l l l 为左边界所能构成的其他水量&#xff0c;与矮的右边界搭配结果如下。 与高的…...

c++高阶-1-模板

文章目录 模板一、模板基本语法二、函数模板1.基本语法2.函数模板注意事项3.普通函数和函数模板区别4.普通函数和函数模板调用规则 三、类模板1.基本语法2.类模板和函数模板的区别3.类模板中成员函数调用时机4.类模板对象做函数参数5.类模板与继承6.成员函数的类外实现 模板 一…...

.net core 的 winform 的 浏览器控件 WebView2

在.NET Core WinForms应用程序中&#xff0c;没有直接的“浏览器控件”&#xff0c;因为WinForms不支持像WebBrowser控件那样的功能。但是&#xff0c;你可以使用WebView2控件&#xff0c;它是一个基于Chromium的浏览器内核&#xff0c;可以在WinForms应用程序中嵌入Web内容。 …...

Django QuerySet对象,all()方法

all()方法 在Django中&#xff0c;all()方法是QuerySet对象的一个方法&#xff0c;用于获取模型的所有实例。 当你调用ModelName.objects.all()时&#xff0c;Django会生成一个SQL查询&#xff0c;从数据库中获取该模型的所有记录&#xff0c;并返回一个QuerySet对象&#xf…...

自动生成网站sitemap

要在 Next.js 和 Contentlayer 项目中实现自动生成 Sitemap 的功能&#xff0c;你可以编写一个脚本&#xff0c;在每次生成文档后自动生成 Sitemap。以下是一个示例脚本&#xff0c;你可以根据自己的需求进行调整。 步骤 1&#xff1a;安装必要的依赖 首先&#xff0c;你需要…...

中国经济昆虫志(55卷)

中国经济昆虫志&#xff0c;共55卷&#xff0c;内容包括概述、形态特征、分类等。各级分类单元均编有检索表&#xff0c;每个种有特征描述、地理分布&#xff0c;有的还记载有生活习性和防治方法。为便于鉴定&#xff0c;绘制有特征图和彩色图。 包括鞘翅目天牛科、半翅目蝽科、…...

linux环境安装elasticsearch缓存数据库和Kibana客户端

linux环境安装elasticsearch缓存数据库&#xff0c;今天我们安装7.17.18版本&#xff0c;并分析遇到的问题。 一、elasticsearch安装运行 1、直接下载 wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.17.18-linux-x86_64.tar.gz2、解压 tar -…...

OpenSSL的一些使用案例

目录 一、介绍 二、基本使用 1、Shell &#xff08;1&#xff09;文件加解密 &#xff08;2&#xff09;生成密钥文件 2、API &#xff08;1&#xff09;md5sum &#xff08;2&#xff09;AES256加解密 一、介绍 本篇博客重点不是详细描述 OpenSSL 的用法&#xff0c;只…...

常用字符串方法<python>

导言 在python中内置了许多的字符串方法&#xff0c;使用字符串方法可以方便快捷解决很多问题&#xff0c;所以本文将要介绍一些常用的字符串方法。 目录 导言 string.center(width[,fillchar]) string.capitalize() string.count(sub[,start[,end]]) string.join(iterabl…...

线程池666666

1. 作用 线程池内部维护了多个工作线程&#xff0c;每个工作线程都会去任务队列中拿取任务并执行&#xff0c;当执行完一个任务后不是马上销毁&#xff0c;而是继续保留执行其它任务。显然&#xff0c;线程池提高了多线程的复用率&#xff0c;减少了创建和销毁线程的时间。 2…...

Python28-5 k-means算法

k-means 算法介绍 k-means 算法是一种经典的聚类算法&#xff0c;其目的是将数据集分成 ( k ) 个不同的簇&#xff0c;每个簇内的数据点尽可能接近。算法的基本思想是通过反复迭代优化簇中心的位置&#xff0c;使得每个簇内的点与簇中心的距离之和最小。k-means 算法的具体步骤…...

主流国产服务器操作系统技术分析

主流国产服务器操作系统 信创 "信创"&#xff0c;即信息技术应用创新&#xff0c;作为科技自立自强的核心词汇&#xff0c;在我国信息化建设的进程中扮演着至关重要的角色。自2016年起步&#xff0c;2020年开始蓬勃兴起&#xff0c;信创的浪潮正席卷整个信息与通信技…...

【Linux】线程封装与互斥(万字)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 C多线程的用法 对原生线程进行一次封装 理解pthread线程 Linux线程互斥 进程线程间的互斥相关背景概念 互斥量mutex 操作共享变量会有问题的售票…...

5分钟教你部署MySQL8.0环境

此方法基于Windows操作系统&#xff01; 一、在MySQL官网单击downloads&#xff08;下载&#xff09;MySQLhttps://www.mysql.com/cn/ 选择在Windows操作系统下载 二、选择合适的版本 推荐下载第二种&#xff0c;安装时离线安装即可 三、安装MySQL8.0 1、找到MySQL下载完成…...

LLM应用:传统NLP任务

LLM出来以后&#xff0c;知乎上就出现了“传统NLP已死”的言论&#xff0c;但是传统NLP真的就被扔进历史的垃圾桶了吗&#xff1f; 其实&#xff0c;尽管LLM具有出色的通用能力&#xff0c;但仍然无法有效应对低资源领域的自然语言处理任务&#xff0c;如小语种翻译。为了更好地…...

基于Hadoop平台的电信客服数据的处理与分析③项目开发:搭建Kafka大数据运算环境---任务11:基础环境准备

任务描述 任务主要是安装配置基础环境&#xff0c;主要内容包括&#xff1a; 1、安装java Kafka和ZooKeeper都需要安装Java环境&#xff0c;推荐至少Java8及以上版本 2、安装ZooKeeper ZooKeeper是Kafka集群的必要组件 3、安装kafka Kafka版本包括使用的scala语言版本和kafka版…...

Golang中swtich中如何强制执行下一个代码块

switch 语句中的 case 代码块会默认带上 break&#xff0c;但可以使用 fallthrough 来强制执行下一个 case 代码块。 package mainimport ("fmt" )func main() {isSpace : func(char byte) bool {switch char {case : // 空格符会直接 break&#xff0c;返回 false…...

读书笔记-Java并发编程的艺术-第4章(Java并发编程基础)-第2节(启动和终止线程)

文章目录 4.2 启动和终止线程4.2.1 构造线程4.2.2 启动线程4.2.3 理解中断4.2.4 过期的suspend()、resume()和stop()4.2.5 安全地终止线程 4.2 启动和终止线程 在前面章节的示例中通过调用线程的start()方法进行启动&#xff0c;随着run()方法的执行完毕&#xff0c;线程也随之…...

通俗大白话理解Docker

什么是Docker Docker本质上是一种容器化技术&#xff0c;用于将应用程序及其所有依赖打包到一个标准化的单元中。这些单元&#xff08;容器&#xff09;可以在任何运行Docker的机器上运行。每个容器是相互隔离的&#xff0c;具有自己的文件系统、网络和进程空间。 以下是大白话…...

题解:CF1981C(Turtle and an Incomplete Sequence)

题解&#xff1a;CF1981C&#xff08;Turtle and an Incomplete Sequence&#xff09; Part 1&#xff1a;题意理解 地址链接&#xff1a;CF、洛谷。题面翻译&#xff1a;给定一个长度为 n n n 的序列 a a a&#xff0c;其中有一些元素未知&#xff0c;用 − 1 -1 −1 表示…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...