继续刷啊刷 11 ～ 装最多水的容器

基本信息

• 题号：11
• 题厂：脸书，谷歌
• 难度系数：中

数组数字代表容器两边的高度，在哪两个容器边界内，可装水做多？

解题思路

• 根据日常水桶原理，装水要以最短的那个边算

• 到了本题，自然就是任选两个边（x 和 y），x 和 y 中较小者为高，x 和 y 之间的横轴距离为底。「底 * 高」为可装水量，遍历所有可装水组合，返回最大值即可
• 如何遍历所有装水组合？brute force 可以，但是采用双指针原理，可以把时间复杂度降低到 O（n）—— 左、右指针相向而行直到交叉为止，在此过程中把最大值找出作为结果返回

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 初始返回值为 0
        res = 0
        
        # 创建左，右双指针，相向而行
        l, r = 0, len(height) - 1
        
        while l < r:
            area = (r - l) * min(height[l], height[r])
            res = max(res, area)

            # 更新最大容水量后，为了获取最大值，移动数值较小的那个指针
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
                
        return res

Constraints

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

本题数据基本于是 brute force 是不行的。考试时，可以向考官确认 n 的最小值。

Big O

• Time：O（n）
• Space：O（1）

测试

• n = 2 
• n 取最大值，测试算法效率
• ……

总结

正常难度中档题。

考点除了要熟悉双指针代码套路，还要反应过来本题可以用双指针思路简化。