基本信息

  • 题号：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 取最大值，测试算法效率
  • ……


总结

正常难度中档题。

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