这题很简单。
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i,
height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：n == height.length
2 <= n <= 105
0 <= height[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water
class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) res = 0 # //双指针首尾逼近遍历，直到两指针相遇 j =n-1 i = 0 while(i<j): res = max(res, (j - i) * min(height[i], height[j])) # 右边高，则右指针不动，左指针往右靠 if height[i]<height[j]: i = i+1 else: j = j-1 # //反之亦然 return res
时间复杂度为O(n),非常神奇。
1.双指针的思想来源
说实话, 第一次看到这道题, 是真的很难想到 双指针 的思想的, 看到一个比较有趣的评论: 所谓的解题思路, 就是你解题解的多了, 自然就有思路了. 对于刷算法而言, 真的是太真实了. 有些题目的思想不会就是不会, 根本不是再努力思考一下就能想到的问题. 所以我们只管更多的刷题再对它们进行总结归纳, 题目刷的多了, 这些巧妙的思想我们自然就会了!
所以我们来总结一下这题的 双指针 思想, 首先最重要的点: 双指针大多都是对两层循环的优化, 所以当暴力法涉及到两层循环遍历的时候, 我们就应该有这种思想: 能不能用到双指针的思想.
其次, 就是要有限制的满足条件, 对于本题而言, 限制的满足条件就是 每次移动数字较小的那个指针, 我们必须根据题目找到某个条件, 而这个条件就是双指针的移动条件, 也是使用双指针思想的基础. 之后我们会通过大量题目的训练来切实的掌握双指针.
2.双指针移动的条件
本题的一个难点就是 双指针移动的条件, 要找到这个条件, 我们就需要从题目的定义出发, 也就是容纳的水量的含义, 当左右指针分别指向数组的左右两端, 那 容纳的水量 = 两个指针指向的数字中较小值 ∗ 指针之间的距离.
接下来我们就只要考虑移动双指针后两者的变化情况即可. 如果我们移动数字较大的那个指针, 那么前者「两个指针指向的数字中较小值」不会增加, 后者「指针之间的距离」会减小, 那么这个乘积会减小, 因此, 我们移动 数字较小的那个指针, 这是从公式的变化角度来解释如何移动指针的, 还是比较容易理解的, 只是思想不太严谨, 如果想更严格的证明, 可以看下面的讲解.
3.双指针合理性的证明
4.两个优化点
本题在上面 双指针 思想的基础上存在两个小的优化点, 对代码的运行速度还是有一定提升的. 思想都挺清晰的, 代码上的实现也并不困难, 就不多解释了:
除此之外就是代码上的区别了: java中的 Math.max/min 对应于 Python中为 max/min, 因为在java中的这两个函数属于Math类下面的方法, 而在Python中这个函数属于系统方法, 用法也是更加强大!
来源：力扣（LeetCode）
