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

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...