11-盛最多的水的容器

11. 盛最多水的容器

双指针

双指针的思想来源

双指针大多都是对两层循环的优化，所以当暴力法设计到两层循环遍历的时候，我们就应该有这种思想：能不能用双指针。

其次，就是要有限制的满足条件，对于本题而言，限制的满足条件就是 每次移动数字较小的那个指针，我们必须根据题目找到某个条件，而这个条件就是双指针的移动条件，也就是双指针思想的基础。

双指针移动的条件

要找到这个条件，我们就需要从题目的定义出发，也就是容纳的水量的含义，当左右指针分别指向数组的左右两端，那么， 容纳的水量 = 两个指针指向的数字中较小的值 x 指针之间的距离。

接下来就只要考虑移动双指针后两者的变化情况即可。如果我们移动数字较大的那个指针，那么前者 【两个指针指向的数字中较小值】不会增加，后者 【指针之间的距离】会减小，那么这个成绩会减小。因此，我们移动数字较小的那个指针，这是从公式变化角度解释如何移动指针的

双指针合理性的证明

双指针的含义：

  • 双指针代表的是，可以作为容器边界的所有位置的范围
  • 在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界。
  • 在这之后，我们每次将，对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我吗任务 这个指针不再能作为容器的边界了。

两个优化点

  • 当任意一边移动后，如果高度低于之前的高度，那么继续移动就行，不需要计算面积和比对两步多余操作。
  • 两边相等时，可以同时移动左右边界，相等的时候，两边界都是瓶颈，就算只移动一侧，移动后得到的容器也受之前瓶颈的影响而只会减小，所以如果想得到更大的容积，同时移动两侧就可以了（同时跳过瓶颈）
1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}