11. Container with most water

题解思路

这道题一开始肯定想到的思路是 Brute Force。

即循环两次，固定 end，然后让 i 从 0 遍历到 end-1，寻找最大的 Area。

面积计算公式为：$$Area=(end-i)\times\min(height[i],height[end])$$

但是如此计算肯定会造成不必要的重复计算。

例如，如果 $height[i] > height[i+1]$

继续向右移动 i 时，宽度变小，而高度也变小，那么这一部分计算其实可以直接跳过。

但是如何修剪 Brute Force 是个问题。如果仍然采用单指针，虽然可以在循环中跳过一部分计算，但最坏情况下复杂度依旧是 $O(n^2)$

那么如何从单指针想到双指针呢？

①这一点是一个类似信仰之跃的东西，首先我们肯定是要覆盖所有的高度和宽度，但是在这个过程中有一些情况是可以跳过的，一个就是上面说的单指针的时候往右走的时候高度减小的情况，而当满足单指针的height[i] > height[end]的情况我们也是可以省略一些步骤的。

假设当前满足：$height[i] > height[end]$

那么当前容器的高度已经确定为 height[right]。

此时如果继续向右移动 i，虽然新的 height[i] 可能变高，但高度不会超过 height[end]，而新的height[i] 可能变矮的情况下，容器高度甚至会小于height[end]，因此：

$min(height[k],height[end])≤height[end], k \in (i, end]$

与此同时，宽度一定会变小：

$k - i \le end - i$

因此新的面积最多只能达到:

$(end - k ) \times min(height[k], height[end])\le (end - i) \times height[end]$

因此，对于当前的 end 而言，再去尝试任何新的 i 都不会得到更大的面积，所以当前 end 已经不用再检查了，可以安全地向左移动。

所以这个时候，我们需要移动 end。

同理，当

$height[i] \le height[end]$

时，可以证明当前 i 已经不用再检查，因此移动 i。

至此，双指针的方法就确定下来了。

1. left = 0，right = length - 1
2. 计算当前面积，并更新最大值：

$$Area=(right-left)\times\min(height[left],height[right])$$

3. 比较两侧高度。
   • 如果 height[left] > height[right]，移动 right（参考①）。
   • 否则移动 left。

最终代码

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        maxArea = 0
        while left < right:
            maxArea = max((right - left) * min(height[left], height[right]), maxArea)
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return maxArea

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        maxArea = 0
        while left < right:
            maxArea = max((right - left) * min(height[left], height[right]), maxArea)
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return maxArea