LeetCode hot 100 — 11. 盛最多水的容器

给定一个长度为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

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

逻辑不难，但写的时候就没有用到所谓的双指针概念，写了一个双重循环，果不其然超时了。

# 自写第一版本代码 class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) res = -1 for i in range(0, n): for j in range(i + 1, n): area = min(height[i], height[j]) * (j - i) res = max(res, area) return res

结果是：

超出时间限制 55 / 65 个通过的测试用例

感觉和上一个三数之和一样，核心是如何剪枝优化，直接去掉非必要的过滤

class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) res = -1 left = 0 right = n -1 while left < right: area = min(height[left], height[right]) * (right - left) res = max(area, res) # 到这里都和上一版本保持一致 # 注意一个点，如果是从两端开始向中间移动的话，此时保证了宽是递减的状态；那么如果area想要增长，高必须增大 ————————> 过滤条件出现 if height[left] < height[right]: left += 1 else: right -= 1 # 确保min(height[left], height[right] 在增大) return res