算法刷题记录 —— 盛最多水的容器
题目链接11.盛最多水的容器问题分析这道题如果只追求O(n²)的实现并不难难点在于如何做到O(n)。我们先来看一下题目的示意图这道题的核心需求非常明确——找到能盛最多水的两条线构成的容器。容量的计算公式很简单面积 长 × 宽其中「宽」由两条线中较短的那条决定木桶效应「长」则是两条线在数组中的下标距离。换句话说对于任意两个位置i和jarea (j - i) × min(height[i], height[j])问题转化为如何快速找到「宽」和「长」的最佳搭配使得乘积最大化O(n²) 暴力解法最直接的思路当然是两重for循环枚举所有可能的线对组合逐一计算面积并更新最大值。代码写起来非常简单但时间复杂度是 O(n²)在数据量较大时会超时。那么为什么暴力解法是 O(n²) 呢原因在于每次只移动一个指针另一个指针固定不动要遍历出所有组合就必须做 n × n 级别的枚举。O(n) 双指针优化 —— 核心思路想要降到 O(n)思路也很直观两个指针都动起来。说起来简单但关键在于——怎么动才能保证不漏掉最大面积的那一组初始状态我们将left指针放在数组头部下标0right指针放在数组尾部下标n-1。此时「长」是最大的但「宽」可能很小——因为两条线中较矮的那条限制了容量。移动策略回到面积公式面积 长 × 宽。在当前状态下无论我们移动哪个指针「长」都会减小。那么我们要做的就是尽量让「宽」变大来弥补「长」的损失。而「宽」受限于两条线中较矮的那一条——根据木桶效应矮的那条才是真正的瓶颈。因此移动策略非常清晰如果height[left] height[right]说明左边的线是瓶颈那就left尝试换一条更高的线否则右边的线是瓶颈那就right--。每移动一步都重新计算当前面积并与全局最大值比较。当left和right相遇时遍历结束。为什么这样不会漏掉最大值因为每次我们舍弃的都是当前较矮的那条边——它和另一条边之间不可能再产生更大的面积了毕竟「长」在缩小而「宽」已经被这条矮边锁死了上限。这种贪心策略保证了我们一定能遍历到最优解。整个过程类似于滑动窗口本质上是一种巧妙的双指针 贪心思想。代码实现classSolution{publicintmaxArea(int[]height){intleft0;intrightheight.length-1;intmax0;while(left!right){// 计算当前面积长 × 宽intarea(right-left)*Math.min(height[left],height[right]);// 移动较短的那条边if(height[left]height[right]){left;}else{right--;}// 更新最大值if(areamax){maxarea;}}returnmax;}}关键点总结面积公式(right - left) × min(height[left], height[right])这是理解整个题目的基础。双指针初始化左右指针分别指向数组的头和尾此时「长」最大。移动策略每次移动较短的那条边这是「木桶效应」的直接体现也是 O(n) 正确性的核心保证。数学函数Math.min()用于获取两条边中的较小值注意积累这类常用 API。复杂度每个元素最多被访问一次时间复杂度O(n)空间复杂度O(1)。这道题的双指针思路非常经典核心在于想清楚「为什么移动较短的那条边不会漏掉最优解」。理解了这一点整道题就豁然开朗了。

相关新闻

3分钟把一张图变成可编辑的PSD分层文件:开源工具LayerDivider上手全记录

3分钟把一张图变成可编辑的PSD分层文件:开源工具LayerDivider上手全记录

3分钟把一张图变成可编辑的PSD分层文件:开源工具LayerDivider上手全记录 【免费下载链接】layerdivider A tool to divide a single illustration into a layered structure. 项目地址: https://gitcode.com/gh_mirrors/la/layerdivider 上周帮朋友救急&…

2026/11/15 12:03:10 阅读更多 →
微信聊天记录备份工具WechatBakTool:一个被下架的开源项目留下的启示

微信聊天记录备份工具WechatBakTool:一个被下架的开源项目留下的启示

微信聊天记录备份工具WechatBakTool:一个被下架的开源项目留下的启示 【免费下载链接】WechatBakTool 基于C#的微信PC版聊天记录备份工具,提供图形界面,解密微信数据库并导出聊天记录。 项目地址: https://gitcode.com/gh_mirrors/we/Wecha…

2026/11/3 21:19:33 阅读更多 →
如何通过Cursor将顶级AI编程助手稳定高效融入开发工作流

如何通过Cursor将顶级AI编程助手稳定高效融入开发工作流

最近在技术社区里,有一个现象挺有意思:一边是很多开发者还在为API调用成本、模型配额和“免费额度用完了怎么办”而精打细算,小心翼翼地使用着各种“平替”模型;另一边,却总能看到一些人,仿佛手握“无限火力…

2026/11/12 17:23:06 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻