1、解题思路

  1. 暴力法：遍历所有可能的两根高度组合，计算每对组合的容积，并记录最大容积。时间复杂度为 O(n^2^)，对于 n=10^5^ 来说，这种方法显然不可行。
  2. 双指针法：使用两个指针，一个指向数组的开始（left），一个指向数组的末尾（right）。计算当前指针所指向的两根高度形成的容积，并更新最大容积。移动指针的策略：移动高度较小的指针，因为这样可以保留较高的高度，有可能获得更大的容积。时间复杂度为O(n)，空间复杂度为O(1)。

2、代码实现

C++
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型vector
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        int left = 0;
        int right = height.size() - 1;
        int max_water = 0;

        while (left < right) {
            int current_water = min(height[left], height[right]) * (right - left);
            max_water = max(max_water, current_water);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max_water;
    }
};
Java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        int left = 0;
        int right = height.length - 1;
        int maxWater = 0;
        
        while (left < right) {
            int currentWater = Math.min(height[left], height[right]) * (right - left);
            maxWater = Math.max(maxWater, currentWater);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
}
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param height int整型一维数组 
# @return int整型
#
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        left = 0
        right = len(height) - 1
        max_water = 0
        
        while left < right:
            current_water = min(height[left], height[right]) * (right - left)
            max_water = max(max_water, current_water)
            
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_water

3、复杂度分析

  1. 双指针法 ：使用两个指针从数组两端向中间移动，每次移动高度较小的指针，这样可以保留较高的高度，有可能获得更大的容积。
  2. 容积计算 ：容积由两个高度中的较小者与它们之间的距离决定，即 min(height[left], height[right]) * (right - left)。
  3. 时间复杂度 ：只需遍历数组一次，时间复杂度为O(n)。
  4. 空间复杂度 ：仅使用常数空间，空间复杂度为O(1)。