如何优化O(n²)暴力解法以解决盛最多水的容器问题？

问题说明 #

用暴力枚举法解决「盛最多水的容器」问题时，仅能通过小规模测试用例，提交时触发TLE（超时）。该解法时间复杂度为O(n²)，无法处理大输入规模，需要优化到更优的时间复杂度。

暴力解法代码 #

class Solution(object):
    def maxArea(self, height):
        ln = len(height)
        max_area = 0
        str_height = list(map(int, height))   # 将所有元素转为整数列表

        for left_index in range(ln):
            left_height = str_height[left_index]

            for right_index in range(left_index + 1, ln):
                right_height = str_height[right_index]
                
                width = right_index - left_index    # 计算两个指针的间距（宽度）

                height_lvl = min(left_height, right_height) # 取两个高度的较小值作为有效高度
                area = width * height_lvl
                max_area = max(area, max_area)
        
        return max_area

注：已将变量重命名为height_lvl以避免与函数参数height混淆。

优化方案：双指针法 #

核心原理 #

盛水面积由两个因素决定：两个指针的间距（宽度） 和 两个指针指向高度的较小值（有效高度）。双指针法通过贪心策略减少无效枚举，核心逻辑如下：

• 初始时，左指针指向数组最左端，右指针指向最右端，此时宽度最大，是所有可能组合中宽度的上限。
• 每次移动高度较小的那个指针：
  • 若移动高度较大的指针，宽度会减小，而有效高度最多等于原来的较小高度，面积必然不会增大；
  • 若移动高度较小的指针，虽然宽度减小，但有可能遇到更高的高度，从而得到更大的有效高度，进而可能得到更大的面积。
• 持续移动指针直到左右指针相遇，过程中记录最大面积即可。

优化后代码 #

class Solution(object):
    def maxArea(self, height):
        max_area = 0
        left = 0
        right = len(height) - 1
        
        while left < right:
            current_width = right - left
            current_height = min(height[left], height[right])
            current_area = current_width * current_height
            max_area = max(max_area, current_area)
            
            # 移动高度较小的指针
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

额外细节 #

• 原代码中str_height = list(map(int, height))是多余操作：LeetCode传入的height参数本身就是整数类型的列表，无需额外转换。
• 双指针法仅遍历数组一次，时间复杂度为O(n)，空间复杂度为O(1)，完全满足题目对时间效率的要求。

内容的提问来源于stack exchange，提问作者Jared McCarthy