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

乘最多水的容器 | 算法 | 给定一个整数数组。有n条垂线。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

news 来源：原创 2025/6/28 12:06:12

在我们日常生活中，蓄水似乎是一个极为朴素的物理行为：两堵墙之间，注入水，看谁能装得更多。可如果换个角度，从算法的视角去看这个问题，它会变得怎样？你是否意识到，这样一个简单的问题背后，隐藏着的是人类在面对“有限资源中寻找最优解”这一命题时，所展现出的智慧与思维模式？

一、从“装水问题”谈起：问题的提出与物理直觉

1.1 题目描述：算法问题的语义抽象

我们被给予一个整数数组 height，其每个元素代表一根垂直于 x 轴的线段的高度。第 i 条线段位于横坐标 i 处。我们要从中选择任意两条线段，以 x 轴为底，线段为侧壁，构成一个“容器”。求这个容器所能容纳的最大水量。

用数学语言表达就是：

给定数组：

我们要找到一对下标，使得：

1.2 物理直觉与几何建模

这道题的本质是一道几何问题。我们可以把每个数看作是平面直角坐标系中的一根垂直线段，其底部在 x 轴上。两个线段与 x 轴围成一个矩形槽，槽的高度取决于较短的那根线段，槽的宽度是两个线段之间的距离。

我们要做的，就是找到这样一对线段，使得这个“槽”的面积最大。

这个问题在现实世界中也有对应，比如修建两个挡水坝，在中间蓄水；又比如数据中心的冷却系统设计中，如何在有限结构中最大限度引导冷却液的流动。

二、暴力算法的尝试：最直接但最慢的方案

2.1 暴力破解：穷尽所有可能

最直观的思路是：我们可以枚举所有可能的左右边界组合，然后计算它们围成的面积，最后取最大值。

伪代码如下：

max_area = 0
for i in range(n):for j in range(i + 1, n):area = min(height[i], height[j]) * (j - i)max_area = max(max_area, area)

2.2 时间复杂度分析

这个算法的时间复杂度是，因为我们对每一对可能的 (i, j) 都进行了面积计算。在最坏情况下，当 n = 10^5 时，计算量为，这是不可接受的。

2.3 空间复杂度

空间复杂度仍为，因为我们没有使用额外空间存储结构。

三、数学建模与优化策略

3.1 关键思想：从局部最优走向全局最优

我们可以采用“双指针”策略：设置两个指针，一个从左边开始（left），一个从右边开始（right）。每次计算当前区间组成的容器面积，然后将较短的那一边向中间移动。为什么？因为移动较短边可能找出更高的线段，从而有机会获得更大的面积。

def maxArea(height):left, right = 0, len(height) - 1max_area = 0while left < right:width = right - lefth = min(height[left], height[right])max_area = max(max_area, width * h)if height[left] < height[right]:left += 1else:right -= 1return max_area

3.2 算法的正确性证明

核心逻辑：我们始终从当前最大可能宽度开始，然后不断减小宽度的同时，尝试找到更高的线段提升高度，以挽救面积的损失。

证明思路：

假设当前区间是 i 到 j，高度分别是 h_i 和 h_j，宽度是 j - i。
如果 h_i < h_j，我们知道以 i 为左边界，任何再往右的线段 h_k（k > i）和 h_j 组成的容器，其宽度必然小于当前宽度。
若我们不移动 i，只移动 j，则高度肯定不会高于当前 h_i，面积只会变小。
因此我们必须移动较短的一边，才有可能找到更高的线段来补偿宽度的损失。

3.3 时间与空间复杂度

时间复杂度：，因为每个元素最多被访问一次。
空间复杂度：。

四、深度剖析：为什么双指针能带来线性优化？

4.1 双指针的经典应用场景

“双指针”是一种极为重要的算法技巧，常用于：

对撞指针（如本题）
快慢指针（如链表中找环）
滑动窗口（如最大子数组和/最小覆盖子串）

其核心思想是：在有序或可比较结构中，通过两个游走指针节省无谓的枚举，达到线性优化的目的。

4.2 为什么移动较短边更优？

一个深刻的数学事实是：面积的计算是由最短边决定的。如果我们保持较短边不动而移动较长边，我们只是在牺牲宽度的同时保持高度不变，甚至更低。因此，为了可能的提升，总是移动较短边是最优策略。

这是一种贪婪策略：我们每一步都想博取最大提升空间。

4.3 与其他优化策略的对比

动态规划不适用：问题不像“最优子结构”那样可以拆解。
分治法也不适合：左右分治无法有效组合两个子区间的面积。
单调栈虽强大，但本题无需维持单调结构。

这正是双指针大显身手的领域。

五、极限测试与边界思维：算法在实际中的鲁棒性

5.1 极小输入

[1, 1] → 结果为 1，边界处理正确。

5.2 极大输入

当数组长度为且元素最大为时，算法仍能线性时间处理，优越性显著。

5.3 高度全相等

[5, 5, 5, 5, 5] → 选择最远的两个线段，宽度最大，面积为 5 * (n-1)。

六、从“装水”到“最优选择”的人类思维模型

6.1 贪婪问题

这道题的本质是一个贪婪问题：每一步都做出当前最优决策，以期达到整体最优。它对应着人类在资源有限的世界中，如何在本地信息指导下做出选择。

6.2 从计算到决策：数学模型的抽象价值

“装水”问题其实是一种资源分配模型：有限的空间，寻找最大利用。这种模型在经济学、运筹学、数据科学中普遍出现。

6.3 短板效应与边界约束

在整个问题中，始终是“较短的那根线”决定着容量。这是著名的“木桶原理”的抽象体现：系统的容量由最短板决定。

七、扩展与变种：问题的泛化与挑战

7.1 三维版本：最大水池问题

给定一个二维矩阵，如何找出围成水池的最大体积？这引出了“接雨水 II”问题。

7.2 动态数据流中的最大容器

如果线段是动态输入的呢？我们能否在滑动窗口中维护最大面积？这里需要引入数据结构，如单调队列。

7.3 多个容器的最大总水量

如果可以选择多个不重叠的容器，如何实现总水量最大？问题转化为区间选择与动态规划的结合。

八、结语

我们不只是为了写一个能通过测试的程序，而是为了培养那种从混沌中提炼规则、从有限中寻找最优的能力。算法，正是这个时代最重要的思维工具之一。

乘最多水的容器 | 算法 | 给定一个整数数组。有n条垂线。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

在我们日常生活中，蓄水似乎是一个极为朴素的物理行为：两堵墙之间，注入水，看谁能装得更多。可如果换个角度，从算法的视角去看这个问题，它会变得怎样？你是否意识到，这样一个简单的问题…...

编程日记 2025/6/28 12:06:12

英伟达有意入股 PsiQuantum，释放战略转向量子计算的重要信号

内容来源：量子前哨（ID：Qforepost） 文丨浪味仙排版丨浪味仙行业动向：1800字丨5分钟阅读 “十五年太早，三十年又太晚，但如果说二十年，我想很多人都会相信。” emmmm&#xff0c…...

编程日记 2025/6/27 15:31:22

【Ubuntu修改串口延时(Latency Timer)为1毫秒(设备拔插或系统重启后自动生效)】

Ubuntu修改串口延时Latency Timer为1毫秒-设备拔插或系统重启后自动生效在Ubuntu系统中，串口设备的延时参数(latency_timer)可以通过udev规则永久修改。以下是完整步骤： 创建udev规则文件 sudo vim /etc/udev/rules.d/99-ftdi-low-latency.rules添加以…...

编程日记 2025/6/27 23:40:38

《量子计算实战》PDF下载

内容简介在加密、科学建模、制造物流、金融建模和人工智能等领域，量子计算可以极大提升解决问题的效率。量子系统正变得越来越强大，逐渐可用于生产环境。本书介绍了量子计算的思路与应用，在简要说明与量子相关的科学原理之后，指…...

编程日记 2025/6/27 23:27:18

Win 系统 conda 如何配置镜像源

通过命令添加镜像源（推荐） 以清华源为例，依次执行以下命令： # 添加主镜像源 conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main # 添加免费开源镜像源 conda config --add channels http…...

编程日记 2025/6/27 23:32:27

[密码学实战]使用C语言实现TCP服务端（二十九）

[密码学实战]使用C语言实现TCP服务端（二十九）引言 TCP（传输控制协议）是互联网通信中最核心的协议之一，它提供可靠的、面向连接的数据传输服务。通过C语言的标准Socket API，开发者可以灵活地实现TCP客户端和服务端程序。本文将详细讲解TCP通信的原理，并提供完整的代码…...

编程日记 2025/6/27 0:28:20

打卡Day34

问题： 背景： 剩余时长总时长 - 必须的计算时长（3秒）。记录间隔、记录次数和剩余时长的关系需要进一步分析。数据观察： 当总epoch为20000时，不同记录间隔对应的记录次数和剩余时长如下： 记…...

编程日记 2025/6/27 11:40:58

谷歌开源医疗领域AI语言模型速递：medgemma-27b-text-it

一、模型概述 MedGemma 是由谷歌开发的一个医疗领域 AI 模型系列，基于 Gemma 3 架构，旨在加速医疗保健相关 AI 应用的开发。该模型系列包含两个主要变体：4B 多模态版本（支持文本和图像理解）以及 27B 纯文本版本&#…...

编程日记 2025/6/27 22:58:27

C++ JSON解析技术详解

一、JSON基础与解析流程 1.1 JSON数据结构 JSON包含两种核心结构（）： 对象：{}包裹的键值对集合数组：[]包裹的值序列 1.2 解析流程 flowchart TDA[加载JSON数据] --> B{数据来源}B -->|字符串…...

编程日记 2025/6/27 23:27:40

多维应用场景的落地实践的智慧园区开源了

智慧园区场景视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。用户只需在界…...

编程日记 2025/6/27 22:47:23

本次参数 llamafactory-cli train \ --stage sft \ --do_train True \ --model_name_or_path /home/qhyz/zxy/LLaMA-Factory/model \ --preprocessing_num_workers 16 \ --finetuning_type lora \ --template deepseek3 \ --flash_attn fa2 \ --dataset_dir data \ --dataset …...

编程日记 2025/6/27 7:43:36

基于SpringBoot的美食分享平台设计与开发（Vue MySQL）

💗博主介绍💗：✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示：文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…...

编程日记 2025/6/27 23:21:45

开闭原则 (Open/Closed Principle, OCP)

定义：一个软件实体应当对扩展开放，对修改关闭。即软件实体应尽量在不修改原有代码的情况下进行扩展问题由来：任何软件都需要面临一个很重要的问题，即它们的需求会随时间的推移而发生变化。因为变化，升级和维护等原因&…...

编程日记 2025/6/27 23:31:01

在 “Linux 9“ 系统快速安装配置RabbitMQ

这是在 “Linux 9” 系统（如 RHEL 9、AlmaLinux 9、Rocky Linux 9）上安装和配置 RabbitMQ 的中文指南。前提条件： 你拥有 sudo 权限。你的系统已连接到互联网。firewalld 是你当前活动的防火墙（在基于 RHEL 的系统上很常见&…...

编程日记 2025/6/27 22:47:22

【brpc】安装与使用

brpc安装与使用 1. brpc是什么2. 安装3. 类与接口介绍3.1 日志输出类与接口3.2 protobuf 类与接口3.3 服务端类与接口3.4 客户端类与接口 4. 使用4.1 同步调用4.2 异步调用 1. brpc是什么 brpc 是用 c语言编写的工业级 RPC 框架，常用于搜索、存储、机器学习、广告、…...

编程日记 2025/6/27 23:20:16

C++：关联容器set容器，multiset容器

set与map不一样之处在于set的键值和时值是一样的，且个元素的值不能重复，容器会根据键的大小默认按升序排序，set底层也是红黑树。 multiset则允许键重复。例如： #include<iostream> #include<set> using namespace…...

编程日记 2025/6/27 23:14:51

Java 调用 GitLab API

前言： 上一篇我们使用了 webhook 的方式获取用户提交代码的信息，本篇我简单分享一下使用 GitLab API 来获取用户提交代码的信息。业务分析： 我们需要统计每一个用户的提交代码的信息，那 GitLab 是否有这样的接口呢&#xff1f…...

编程日记 2025/6/27 23:26:49

“智”斗秸秆焚烧，考拉悠然以科技之力筑牢生态安全防线

清晨，薄雾笼罩着辽阔的田野，农民们开始了一天的劳作。然而，随着收割季的到来，秸秆焚烧问题也逐渐浮现，成为威胁空气质量与生态安全的隐患。传统监管方式往往显得力不从心，效率低下的困境亟待突破。在此背景…...

编程日记 2025/6/27 23:06:57

数据库基础面试题（回答思路和面试建议）

以下是针对这些数据库基础问题的详细回答思路和面试回答建议，结合理论、应用场景和实际项目经验展开说明： 1. 数据库三大范式是什么？实际项目中是否需要严格遵循？ 回答思路： 先解释三大范式（逐层递进&…...

编程日记 2025/6/28 5:59:34

数据库blog5_数据库软件架构介绍（以Mysql为例）

🌿软件的架构 🍂分类软件架构总结为两种主要类型：一体式架构和分布式架构 ● 一体化架构一体式架构是一种将所有功能集成到一个单一的、不可分割的应用程序中的架构模式。这种架构通常是一个大型的、复杂的单一应用程序，包含所…...

编程日记 2025/6/27 23:31:54

mysql可重复读隔离级别下的快照读和当前读

在MySQL的可重复读隔离级别下，快照读和当前读是两种不同的读取方式，它们的特点和应用场景有所不同。快照读定义：快照读是指在事务中读取数据时，读取的是事务开始时的历史版本数据，而非当前最新的数据。实现原理&…...

编程日记 2025/6/27 23:18:31

MySQL 单表与多表操作详解

🎈边走、边悟🎈迟早会好目录一、单表查询整合 （一）通用模板展示 （二）举例说明 1. 简单查询 2. 条件查询 3. 高级查询 （三）注意事项 （四）Mapper 简…...

编程日记 2025/6/27 23:26:08

Spring概念问题详解

一、Bean的生命周期 1.1 BeanDefinition Spring容器在进行实例化时，会将xml配置的<bean>的信息封装成一个BeanDefinition对象，Spring根据BeanDefinition来创建Bean对象，里面有很多的属性用来描述Bean。 beanClassName：be…...

编程日记 2025/6/27 22:59:35

使用pm2 部署react+nextjs项目到服务器

记录一下 next.config.js中： output: standalone,package.json配置： "scripts": {"dev": "cross-env NODE_OPTIONS--inspect next dev","build": "next build","start": "cp -r .nex…...

编程日记 2025/6/27 23:33:15

JVM常量池（class文件常量池，运行时常量池，字符串常量池）

文章目录问题JVM运行时数据区JVM中的常量池Class文件常量池运行时常量池字符串常量池创建了几个对象String的定义intern()问题超过1W字深度剖析JVM常量池（全网最详细最有深度） - 跟着Mic学架构 - 博客园问题 jdk1.8之后元空间是独立存在的&#xf…...

编程日记 2025/6/27 17:50:51

Java 大视界 -- 基于 Java 的大数据分布式存储在视频会议系统海量视频数据存储与回放中的应用（263）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/6/27 23:15:26

光谱相机在地质勘测中的应用

一、‌矿物识别与蚀变带分析‌ ‌光谱特征捕捉‌ 通过可见光至近红外（400-1000nm）的高光谱分辨率（可达3.5nm），精确识别矿物的“光谱指纹”。例如： ‌铜矿‌：在400-500nm波段反射率显著低于围…...

编程日记 2025/6/27 23:37:00

深入解析Java泛型：从定义到实战应用

目录 🚀前言🤔泛型的定义🐧泛型类🌟泛型接口✍️泛型方法、通配符、上下限💯泛型方法💯 通配符与上下限⚙️通配符（Wildcard）⚙️泛型上下限⚙️应用场景 🦜泛型支持的类…...

编程日记 2025/6/27 23:01:58

数据结构：绪论之时间复杂度与空间复杂度

作者主页失踪人口回归，陆续回三中。开辟文章新专栏——数据结构，恳请各位大佬批评指正！ 文章目录作者主页数据结构的基本知识数据：数据元素：数据对象：数据类型：数据结构：逻辑结…...

编程日记 2025/6/27 23:38:36

ARM Linux远程调试

准备虚拟机既能ping通开发板，又能ping通外网，还要能ping通Windows主机（如果你有上位机通信（tftp、vsftp、ssh）的需求） VMware 添加网络适配器2用作桥接网卡，原有的网络适配器保持为NAT模式打开虚拟网络编辑器，配置VMnet0为桥接模式，外部连接设置为Realtek PCIe G…...

编程日记 2025/6/27 18:06:07

PostgreSQL 14 pacemaker 高可用集群

核心架构原理集群组成（典型三节点结构）： [Node1] PostgreSQL Pacemaker Corosync pcsd [Node2] PostgreSQL Pacemaker Corosync pcsd [Node3] PostgreSQL Pacemaker Corosync pcsd ↕ ↕ ↕ ← Corosync 多…...

编程日记 2025/6/27 15:15:56

英语学习5.21

Far from sensible 表示“很不明智的”、“离明智相去甚远”。这是一个固定表达，结构是 far from adj.，意思是“根本不……”，常见例子： far from perfect（远非完美） far from acceptable（远…...

编程日记 2025/6/27 23:00:44

实现了TCP的单向通信

1. 客户端代码：Client.java package com.xie.javase.net1;import java.io.*; import java.net.*;public class Client {public static void main(String[] args) {Socket socket = null;BufferedWriter bw = null;try {// 1. 获取本机IP地址对象InetAddress localHost = Inet…...

编程日记 2025/6/27 23:19:34

华为云Flexus+DeepSeek征文 | 基于ModelArts Studio和Cherry Studio快速构建午餐管家助手

目录一、前言二、ModelArts Studio（MaaS）介绍与应用场景 2.1ModelArts Studio（MaaS）介绍 2.2 ModelArts Studio（MaaS）使用场景 2.3 开通MaaS服务 2.4 开通DeepSeek-V3商用服务三、Cherry Studio简介和安…...

编程日记 2025/6/27 19:04:03

Spring AI 1.0 GA 正式发布

Spring AI 1.0 GA 正式发布快速入门核心特性1. **增强型 LLM（大语言模型）**2. **MCP 协议支持**3. **RAG（检索增强生成）**4. **评估与监控**5. **智能代理（Agents）** 下一步计划 VMware Spring 团队 Mark …...

编程日记 2025/6/27 23:13:12

【计算机网络第8版】谢希仁编著第五章运输层题型总结1 UDP和TCP报文格式

UDP报文 5.13 这一题可以先问AI： 但是问了AI，肯定想知道：这些知识点在书上哪里？怎么这么难找？ 没错这题主要是靠IP地址，所以应该在第四章。 P136 P137 省流： 1.UDP的首部格式是8个字节&…...

编程日记 2025/6/28 3:58:17

华为云Flexus+DeepSeek征文 | 基于ModelArts Studio 的 DeepSeek API 实现行业深度搜索和分析

目录一、前言二、ModelArts Studio（MaaS）介绍与应用场景 2.1ModelArts Studio（MaaS）介绍 2.2 ModelArts Studio（MaaS）使用场景 2.3 开通MaaS服务 2.4 开通DeepSeek-V3商用服务三、Deep Research简介和安…...

编程日记 2025/6/27 23:02:09

计算机网络——Session、Cookie 和 Token

在 Web 开发中，Session、Cookie 和 Token 是实现用户会话管理和身份验证的核心技术。它们既有联系，也有明显区别。以下从定义、原理、联系、区别和应用场景等方面详细解析。一、基本定义与原理 1. Cookie 定义： 是浏览器存储在客户端的小…...

编程日记 2025/6/27 23:00:26

AAOS系列之----简介

一文讲透AAOS架构，点到为止不藏私 📌 AAOS是以一个系统APP的方式集成进安卓系统中,通过在SystemServer中启动其中的Service 📚 1. CarServcie 是如何被启动的？ AAOS中的核心服务是CarService,其描述如下: 代码路径如下: android1…...

编程日记 2025/6/27 17:50:29

CTF签到题

1.题目：VmxkMFUxVXhTbkpOU0dSVVZrWktWRlpyVm5kU2JGSnlWbXhhYkdKRlduaFpWVlpoVkcxRmQwMUlhRlpXTTFKUVZXdFZlR05zWkZsaVJrcG9ZbGRvUmxaR1dsZFVhekZIVW14V1lWSlZOVkJVVlZaV1RVWldjbFZzVGxOTlJGWlhWa1pvZDFWdFJuTlRhMVpXVm14YVIxUlVSa2RPYkVweVYyeENWMVpVUlhwV1ZtUjNVMj…...

编程日记 2025/6/27 22:47:31

甲骨文云服务器适合做网站吗

甲骨文云服务器：建网站，它到底是不是“神队友”？ 各位想在网上“立门户”的老板、个人创作者们，大家好！现在这年头，没个自己的网站，那感觉就像做生意没个店面、搞创作没个画廊一样，…...

编程日记 2025/6/27 23:04:16

性能测试场景题

题目针对618，双十一活动的，一个电商系统，如何设计压力测试方案？ 参考答案针对618、双十一等高并发电商大促活动，压力测试方案需覆盖全链路性能瓶颈识别、容量评估和极端场景验证。以下为详细设计框架，…...

编程日记 2025/6/27 23:02:25

数智读书笔记系列033《软件设计的哲学（第2版）》：复杂性管理的艺术

《软件设计的哲学》（A Philosophy of Software Design）书籍简介作者：约翰奥斯特豪特（John Ousterhout）出版信息：第2版于2024年11月由人民邮电出版社出版，中文版由茹炳晟、王海鹏翻译。作者背景奥斯特豪特是斯坦福大学计算机科学教授、美国国家工程院院士，拥有丰…...

编程日记 2025/6/27 23:18:55