题目
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[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提示
一句话思路：双指针从两端向中间收缩，每次只移动「较矮」的那一边，因为容器的水量由较矮的一边决定。
- 水量 =
min(height[i], height[j]) * (j - i)，短板决定高度。 - 如果固定较高的那一边去移动，宽度在减小而高度不可能变高，水量只会更小，所以保留高的一边，移动矮的一边才可能找到更大值。
- 每个位置只会被访问一次，时间复杂度 O(n)，空间 O(1)。
答案
python
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j, res = 0, len(height) - 1, 0 # i、j 左右指针；res 记录最大水量
while i < j: # 两指针未相遇就继续
if height[i] < height[j]: # 左边更矮，左板决定水量，移动左边才可能变大
res = max(res, height[i] * (j - i)) # 计算当前水量并更新最大值
i += 1 # 移动较矮的左指针
else: # 右边更矮（或相等）
res = max(res, height[j] * (j - i)) # 计算当前水量并更新最大值
j -= 1 # 移动较矮的右指针
return res # 返回最大水量
留言板