👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化：企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

“容纳最多水的容器”是一个经典的数组和双指针问题，考验的是对空间利用和指针操作的理解。本文将通过不同的算法解决这个问题，并提供代码示例及详细的解题步骤。

问题描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

注意：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：数组中的第二个和最后一个元素形成的容器可以容纳最多的水，其面积为 49。

解题思路

方法一：暴力法

最直观的方法是尝试所有可能的两点组合，计算它们能形成的容器的面积，然后找出最大值。

解题步骤

1. 遍历每一对索引组合 (i, j)，其中 0 <= i < j < n。
2. 对每对索引计算容器的面积：Area = min(height[i], height[j]) * (j - i)。
3. 记录并更新最大面积。

python示例

def maxArea_v1(height: [int]) -> int:
    max_area = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)
    return max_area

复杂度分析：

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

方法二：双指针法

双指针法是解决这个问题的最佳方法，它利用了“向内移动短板可以找到可能的更大面积”的直觉。

解题步骤

1. 初始化两个指针分别指向数组的开头和结尾。
2. 计算当前两个指针形成的容器的面积，并更新最大面积。
3. 移动较短的一边的指针向内，直到两个指针相遇。

python示例

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

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

双指针图解

初始状态

设想一个容器的左右边界由线段的两端组成。此时，左指针在数组的最开始位置（索引 0），右指针在数组的最末尾位置（索引 len(height) - 1）。这个容器的宽度是最大的。

  [1,8,6,2,5,4,8,3,7]
   ^               ^
   |               |
 left           right

移动指针

接下来，我们比较左右指针指向的高度。为了增加容器的高度，我们总是向内移动较矮的边，因为容器的实际高度由较矮的那边决定。在每一步中，我们计算当前指针指向的容器能容纳的水量，并更新最大值。

如果左边较矮：

[1,8,6,2,5,4,8,3,7]
   ^             ^
  left         right

如果右边较矮：

如果在某一步中，右指针指向的高度小于左指针指向的高度，那么我们移动右指针向左一位。

[1,8,6,2,5,4,8,3,7]
   ^           ^
  left       right

结束条件

当左右指针相遇时，我们已经考虑了所有可能的容器，循环结束。

总结

“容纳最多水的容器”问题通过暴力法可以直观地理解问题，但双指针法在效率上大大提升，是解决这类问题的典型示例。学会双指针技巧不仅可以帮助我们优雅地解决这个问题，也是提升算法解题能力的重要手段。