盛最多水的容器

题解思路

本题的目标是找到两条竖线，使得它们与x轴形成的容器能容纳最多的水。水的容量由 较短的竖线高度 和 两条竖线的横坐标距离 决定，即：

$\text{容积}$$= \min(\text{height}[left], \text{height}$$[right]) \times (\text{right} - \text{left})$

最直观的解法是 暴力枚举 两条竖线的所有可能组合，但时间复杂度为 $O(n^2)$，会超时。

双指针优化

由于水的容量受限于 较短的竖线高度，我们可以使用 双指针法 来优化：

1. 初始化：左右指针分别放在数组的最左和最右。
2. 计算当前容积，记录最大值。
3. 移动指针：
   • 如果 height[left] < height[right]，移动左指针 left++（因为容量受短板影响，试图寻找更高的左边界）。
   • 否则，移动右指针 right--（寻找更高的右边界）。
4. 重复 直到 left == right。

这样，每个元素最多被访问一次，总时间复杂度为 $O(n)$，是最优解法。

复杂度分析

• 时间复杂度：$O(n)$，每个元素最多被访问一次。
• 空间复杂度：$O(1)$，只使用了常数级别的变量。

代码实现

Python 代码

class Solution:
    def maxArea(self, height):
        """
        双指针法求解最大容积
        :param height: List[int] 代表垂线的高度数组
        :return: int 最大水容量
        """
        left, right = 0, len(height) - 1  # 初始化左右指针
        max_area = 0  # 记录最大面积
        
        while left < right:
            # 计算当前区域的容量
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)
            
            # 移动短板
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

# 读取输入
if __name__ == "__main__":
    n = int(input())  # 读取整数 n
    height = list(map(int, input().split()))  # 读取数组
    solution = Solution()
    print(solution.maxArea(height))

Java 代码

import java.util.Scanner;

public class Main {
    public class Solution {
        public int maxArea(int[] height) {
            int left = 0, right = height.length - 1;
            int maxArea = 0;

            while (left < right) {
                // 计算当前容积
                int area = Math.min(height[left], height[right]) * (right - left);
                maxArea = Math.max(maxArea, area);

                // 移动较短的边
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取 n
        int[] height = new int[n];
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }
        scanner.close();

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.maxArea(height));
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算当前容积
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);

            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
};

int main() {
    int n;
    cin >> n; // 读取 n
    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }

    Solution solution;
    cout << solution.maxArea(height) << endl;
    
    return 0;
}

题目内容

给定一个长度为$n$的整数数组$height$ 。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i, 0)$ 和 $(i, height[i])$ 。

找出其中的两条线，使得它们与 $x$轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明: 你不能倾斜容器。

输入描述

输出描述

样例1

输入

9
1 8 6 2 5 4 8 3 7

输出

49

说明

图中垂直线代表输入数组$[1,8,6,2,5,4,8,3,7]$。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 $49$。

样例2

输入

2
1 1

输出

1

提示

• $n == height.length$
• $2 <= n <= 10^5$
• $0 <= height[i] <= 10^4$