盛最多水的容器：双指针法的艺术与科学

立志进大厂！

1203人浏览 · 2025-09-09 23:19:01

立志进大厂！ · 2025-09-09 23:19:01 发布

在计算机科学的世界里，总有一些问题如同精致的谜题，看似复杂却藏着简洁优雅的解法。"盛最多水的容器" 正是这样一道经典题目，它不仅是技术面试中的常客，更完美诠释了双指针算法的精妙之处。今天，我们就来深入探索这个问题，感受从暴力求解到高效算法的思维跃迁。

问题解析：从生活到数学

想象一排高度不等的垂直挡板，我们需要选择其中两块，用它们和地面围成一个容器，使其能容纳最多的水。这个问题的核心在于理解容器容量的决定因素：

宽度：两块挡板之间的水平距离
高度：两块挡板中较矮那一块的高度（因为水会从较矮的一侧溢出）

用数学公式表达，容量可以表示为：

容量 = min(height[i], height[j]) × (j - i)

其中 height 是存储挡板高度的数组，i 和 j 是两个挡板的索引（i < j）。我们的目标就是找到使这个公式结果最大的 i 和 j 组合。

解决方案的演进

暴力枚举：直观但低效

最直接的思路是尝试所有可能的挡板组合，计算它们的容量并记录最大值：

def maxArea_brute_force(height):
    max_area = 0
    n = len(height)
    for i in range(n):
        for j in range(i+1, n):
            area = min(height[i], height[j]) * (j - i)
            if area > max_area:
                max_area = area
    return max_area

这种方法的时间复杂度是 O (n²)，当 n 很大（比如 10⁴ 以上）时，计算量会急剧增加，难以在有效时间内得到结果。在算法设计中，我们始终追求更优的时间复杂度，这就需要我们深入理解问题本质，寻找更巧妙的解法。

双指针法：洞察问题本质

高效算法的关键往往在于发现问题中的隐含规律。双指针法正是基于对 "盛水容器" 问题的深刻洞察而设计的：

def maxArea(height):
    left, right = 0, len(height) - 1  # 初始化左右指针
    max_area = 0
    
    while left < right:
        # 计算当前容量
        current_area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, current_area)
        
        # 移动高度较小的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area

这个算法的核心在于指针移动的策略：总是移动高度较小的那个指针。为什么这样做是有效的？让我们来分析一下：

容器的容量由两个因素决定：高度（较矮挡板）和宽度（指针间距）。当我们移动指针时，宽度必然减小，此时要想获得更大的容量，必须提高高度。

如果移动较高的指针，新的高度最多只能保持不变（由较矮的指针决定），而宽度减小，容量必然变小
如果移动较矮的指针，虽然宽度减小，但有可能遇到更高的挡板，从而提高高度，获得更大的容量

这种策略确保了我们不会错过任何可能获得更大容量的机会，同时将时间复杂度降低到了 O (n)。

多语言实现

算法的核心思想是通用的，我们可以用不同的编程语言来实现这个双指针解法：

Java 实现

public class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            int currentHeight = Math.min(height[left], height[right]);
            int currentArea = currentHeight * (right - left);
            maxArea = Math.max(maxArea, currentArea);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

C++ 实现

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int max_area = 0;
        
        while (left < right) {
            int h = min(height[left], height[right]);
            max_area = max(max_area, h * (right - left));
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};

JavaScript 实现

var maxArea = function(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        const currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
};

Go 实现

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    
    for left < right {
        h := min(height[left], height[right])
        area := h * (right - left)
        if area > maxArea {
            maxArea = area
        }
        
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}