问题

11.盛最多的水

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7]

输出：49

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

练习

盛最多的水

# your python code

思路

北海啊，要多想！

该问题关键在于在数组中选择两个位置 i 和 j（i < j），使得容量 min(height[i], height[j]) * (j - i) 最大。

采用暴力解法可以遍历出这两个最佳位置。为优化寻找过程，我们考虑双指针：注意到容量由较短边决定，移动较长边只会让宽度减少而高度不会增加，容量必然不会增大。

因此，双指针的流程如下：

• 从数组两端开始，用两个指针 left 和 right 。
• 每次移动高度较小的指针，并更新面积最大值。

Java

import java.util.Scanner;  
  
public class MaxArea {  
  
    public static void main(String[] args) {  
        // int[] height = {1,8,6,2,5,4,8,3,7};  
        // int[] height = {1,2,1};
         
        // ACM 模式  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
        int[] height = new int[n];  
  
        for (int i = 0; i < n; i++) {  
            height[i] = scanner.nextInt();  
        }  
  
        System.out.println(maxArea(height));  
    }  
    private static int maxArea(int[] height) {  
        int n = height.length, ans = 0;  
        int l = 0, r = n - 1;  
  
        while (l < r) {  
            // 总是移动较小的  
            if (height[l] < height[r]) {  
                ans = Math.max(ans, (r - l) * height[l++]);  
            } else {  
                ans = Math.max(ans, (r - l) * height[r--]);  
            }        
        }  
        return ans;  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(N)$。
• 空间复杂度：$\mathcal{O}(1)$。