尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

【算法日记 17】LeetCode 11. 盛最多水的容器:双指针与贪心思维的完美碰撞

【算法日记 17】LeetCode 11. 盛最多水的容器:双指针与贪心思维的完美碰撞
📅 发布时间:2026/7/8 1:22:34

📍 题目背景

今天我们来啃一块算法面试中的硬骨头,也是极其经典的双指针大题:[11. 盛最多水的容器]。 这道题的官方描述有很多“坐标轴”、“垂线”之类的数学术语,很多新手一看就晕了。但其实,我们完全可以把它当成一个“挑木板拼鱼缸”的游戏!

【大白话题目描述】给你一排高低不平的木板(数组height),让你从中挑出两块木板作为鱼缸的左右两面墙。 你的目标是:找出哪两块木板拼成的鱼缸,能装下最多的水!(注意:水能装多高,取决于两块木板中较矮的那一块,也就是著名的“木桶效应”。)

【示例】

输入:[1,8,6,2,5,4,8,3,7]输出:49解释:选高度为 8 和高度为 7 的两块木板,宽度为 7,高度取矮的 7,最大面积7 * 7 = 49。

✨ 核心破题逻辑:左右指针的“贪心博弈”

为了让鱼缸装最多的水,我们需要让宽度尽量大,同时高度也尽量高。 如果是暴力解法,两两组合去算面积,时间复杂度是 $O(N^2)$,在数据量大的时候必然会超时。

这就需要祭出我们的降维打击绝招:对撞双指针(左右指针)!

1. 初始状态:霸占最大宽度

我们让左指针left站在最左边,右指针right站在最右边。此时,鱼缸的宽度是最大的!算出一个初始面积,记录下来。

2. 灵魂拷问:接下来该挪哪块木板?

既然要往中间找,我们每一次只能移动一块木板。到底该挪高的那一块,还是矮的那一块? 我们来推演一下:

  • 如果挪动高的木板:宽度变小了。而水的高度永远受限于那块没动的“矮木板”。所以,不管新找的木板有多高,水位都不可能超过原来的矮木板。结论:挪高木板,面积一定会变小,纯属血亏!

  • 如果挪动矮的木板:宽度虽然变小了,但是我们有可能遇到一块超级高的木板!这样一来,水位大幅提升,增加的高度完全可能弥补宽度的损失,从而创下面积新高!结论:挪矮木板,才有一线生机搏一把大的!

破题口诀:算完面积,谁矮,就无情地抛弃谁,让它往中间走一步寻找更高的木板!

💻 C++ 满分 AC 代码

掌握了上面的贪心逻辑,代码写起来简直行云流水,极其优雅:

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int maxArea(vector<int>& height) { // 🚀 绝招:左右指针 int left = 0; // 左边的木板 int right = height.size() - 1; // 右边的木板 int max_area = 0; // 记录历史最大水量 // 当两块木板还没有相遇的时候,不断往中间挤 while (left < right) { // 1. 算宽度 (下标相减) int width = right - left; // 2. 算高度 (木桶效应,取决于矮的那块) int current_height = min(height[left], height[right]); // 3. 算当前容量,并看看有没有破纪录 int current_area = width * current_height; max_area = max(max_area, current_area); // 4. 核心贪心抉择:抛弃矮木板,去寻找更高的! if (height[left] < height[right]) { left++; // 左边矮,左边往右走一步寻找生机 } else { right--; // 右边矮,右边往左走一步寻找生机 } } return max_area; } };

🔍 复杂度深度剖析

  • 时间复杂度:$O(N)$。双指针left和right分别从两头往中间走,每次循环必定会淘汰一块木板(移动一个指针)。当两个指针相遇时遍历结束,所以整个数组最多只会被扫描一次。这比 $O(N^2)$ 的暴力解法快了几个数量级!

  • 空间复杂度:$O(1)$。我们只借用了left、right、max_area等几个整型变量来记录状态,完全没有开辟任何新的数组或哈希表空间,内存消耗做到了极致的精简。

💡 总结:这道题是“双指针”结合“贪心思想”的巅峰之作。它的精髓不在于代码有多复杂,而在于那个直击灵魂的数学逻辑——“在确定性(宽度缩小)中,去寻找唯一可能打破天花板的变量(抛弃短板)”。吃透这个逻辑,以后遇到类似求极值的问题,你都能一击必杀!

相关新闻

  • 比特的旅行:自信息、熵、信道容量……一个单位如何丈量整个信息世界
  • Python打包终极指南:用Auto-Py-To-Exe快速创建可执行文件
  • 5个实用技巧:如何使用WebToEpub高效将网页小说转换为电子书

最新新闻

  • 基于HarmonyOS的情侣美食管理应用开发实战(三)- 美食相册与设置功能
  • 设备机箱定制厂家如何提升客户满意度
  • 固态硬盘台式怎么安装在笔记本身上?
  • 【单片机毕业设计】基于 STM32 单片机与 NRF24L01 的四路无线继电器控制系统设计,基于 51 单片机与 NRF24L01 的无线多路开关控制装置设计(020701)
  • Python 装饰器:FastAPI 路由背后的“智能包装流水线”
  • 第2篇:策略模式三大角色拆解与UML

日新闻

  • PROPKA 3深度解析:蛋白质pKa预测的实战指南与算法原理
  • 微信小程序 globalData 监听:基于 Object.defineProperty 的 3 种实现方案对比
  • MySQL 8.0 数据清洗实战:3类异常值识别与 UPDATE/DELETE 批量处理

周新闻

  • 基于YOLOv12的番茄成熟度智能检测系统开发
  • 终极RimWorld模组管理指南:用RimSort告别模组冲突烦恼
  • AI Agent框架开发:从理论到实践的完整指南

月新闻

  • 2026年6月公司网站搭建最新热门渠道测评:四大低成本/零代码平台对比+避坑
  • 【Linux】Linux arm 编译QT程序,出现expected “}“报错
  • 【MATLAB例程】四基站二维AOA定位与距离辅助增强对比仿真。基于角度观测和测距修正的固定目标平面定位精度分析

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号