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

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...