此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
文章目录
- 0.导图整理
- 1.双指针的思想来源
- 2.双指针移动的条件
- 3.双指针合理性的证明
- 4.两个优化点
- 5.有趣评论
- 源码
- Python:
- java:
题目链接: https://leetcode-cn.com/problems/container-with-most-water/solution/si-wei-dao-tu-zheng-li-shuang-zhi-zhen-d-tkx5/
0.导图整理
1.双指针的思想来源
说实话, 第一次看到这道题, 是真的很难想到 双指针 的思想的, 看到一个比较有趣的评论: 所谓的解题思路, 就是你解题解的多了, 自然就有思路了. 对于刷算法而言, 真的是太真实了. 有些题目的思想不会就是不会, 根本不是再努力思考一下就能想到的问题. 所以我们只管更多的刷题再对它们进行总结归纳, 题目刷的多了, 这些巧妙的思想我们自然就会了!
所以我们来总结一下这题的 双指针 思想, 首先最重要的点: 双指针大多都是对两层循环的优化, 所以当暴力法涉及到两层循环遍历的时候, 我们就应该有这种思想: 能不能用到双指针的思想.
其次, 就是要有限制的满足条件, 对于本题而言, 限制的满足条件就是 每次移动数字较小的那个指针, 我们必须根据题目找到某个条件, 而这个条件就是双指针的移动条件, 也是使用双指针思想的基础. 之后我们会通过大量题目的训练来切实的掌握双指针.
2.双指针移动的条件
本题的一个难点就是 双指针移动的条件, 要找到这个条件, 我们就需要从题目的定义出发, 也就是容纳的水量的含义, 当左右指针分别指向数组的左右两端, 那
容纳的水量 = 两个指针指向的数字中较小值 ∗ 指针之间的距离
.
接下来我们就只要考虑移动双指针后两者的变化情况即可. 如果我们移动数字较大的那个指针, 那么前者「两个指针指向的数字中较小值」不会增加, 后者「指针之间的距离」会减小, 那么这个乘积会减小, 因此, 我们移动 数字较小的那个指针, 这是从公式的变化角度来解释如何移动指针的, 还是比较容易理解的, 只是思想不太严谨, 如果想更严格的证明, 可以看下面的讲解.
3.双指针合理性的证明
在证明之前先来理解双指针所代表的含义:
之后就是定量的证明过程了, 过程并不复杂, 就不多解释了:
4.两个优化点
本题在上面 双指针 思想的基础上存在两个小的优化点, 对代码的运行速度还是有一定提升的. 思想都挺清晰的, 代码上的实现也并不困难, 就不多解释了:
除此之外就是代码上的区别了: java中的 Math.max/min 对应于 Python中为 max/min, 因为在java中的这两个函数属于Math类下面的方法, 而在Python中这个函数属于系统方法, 用法也是更加强大!
5.有趣评论
看题解的时候, 发现了几条挺有趣的评论, 如果你还是不太理解双指针的移动条件的话, 可以看下这些评论, 也许对你的理解很有帮助!
源码
Python:
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]: # 移动较小的那一端
l += 1
else:
r -= 1
return ans
java:
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) { // 移动较小的那一端
++l;
}
else {
--r;
}
}
return ans;
}
}
我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)
最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)
最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)
红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理
人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
东南大学 软件工程 复试3门科目历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
高等数学 中值定理 一张思维导图解决中值定理所有题型
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
Spring springmvc Mybatis jsp
科技相关 小米手机
小米 红米 历代手机型号大全 发布时间 发布价格
常见手机品牌的各种系列划分及其特点
历代CPU和GPU的性能情况和常见后缀的含义 思维导图整理