LC11. 盛水最多的容器

题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

题目解析

题目在说什么

想象你面前有一排高度不同的柱子，每个柱子都立在x轴的一个整数点上。比如第一个柱子高度是1，立在x=1的位置；第二个柱子高度是8，立在x=2的位置……一直到第n个柱子。

现在你要从这些柱子中选出两根，把它们当作容器的左右壁。这两根柱子之间形成一个“容器”，容器底部就是x轴。容器能装多少水呢？水的容量取决于两个因素：

• 宽度：两根柱子之间的距离（x坐标差）
• 高度：两根柱子中较短的那根的高度（因为水会从矮的那边溢出去）

面积 = 宽度 × 高度

你的任务就是找到哪两根柱子组合，能让这个面积最大。

思路是怎么来的

先试试最笨的办法：把所有可能的柱子对都算一遍面积，然后找出最大的。但这样太慢了，比如有1000根柱子，就要算大约50万次，电脑会累坏的。

那怎么更快呢？ 我们来想个生活场景：

假设你面前有两根柱子，一根很矮（比如高度2），一根很高（比如高度10），它们相距很远。现在你想让容器装更多水，你会怎么做？

• 如果你把高的那根往矮的那边移动一点，宽度变小了，高度呢？因为水面高度由矮的那根决定，所以高度最多还是2（如果遇到更矮的柱子，高度还会更小）。宽度变小，高度不增加，面积肯定变小。
• 如果你把矮的那根往高的那边移动一点，宽度虽然也变小了，但高度有可能变大（比如遇到一根更高的柱子，水面就能升上去）。虽然宽度变小了，但高度可能变大很多，所以面积有可能变大。

所以聪明的做法是：每次只移动较短的那根柱子，因为只有这样才能有机会让面积变大。

总结一下这个策略： 1. 一开始，我们选择最左边和最右边的柱子，这样宽度最大。 2. 计算当前面积，记录下来。 3. 然后移动较短的那根柱子（向内移动），因为移动高的那根只会让面积变小或不变。 4. 移动后，再计算新面积，和之前记录的最大值比较，保留大的那个。 5. 重复这个过程，直到两根柱子相遇。

这个思路就像“保大放小”——我们永远放弃较短的柱子，去赌另一边可能有更高的柱子。

代码逐步拆解

现在来看代码，我会一行一行解释它在干什么。

class Solution {
    public int maxArea(int[] height) {

这里定义了一个方法，它接收一个整数数组height，数组里每个元素就是每根柱子的高度。

        int left = 0;
        int right = height.length - 1;

left和right是两个“指针”，分别指向数组的第一个元素（最左边的柱子）和最后一个元素（最右边的柱子）。这样一开始我们就让容器宽度最大。

        int res = 0;

res用来记录到目前为止找到的最大面积，初始值为0（因为还没开始算）。

        while(left < right){

只要left还在right左边，我们就继续尝试。如果它们相遇了（left == right），说明只剩一根柱子了，没法构成容器，循环结束。

            int width = right - left;

当前两根柱子的距离就是宽度。注意：因为柱子立在整数点上，所以距离就是坐标差。

            int h = Math.min(height[left], height[right]);

水的高度由较短的那根柱子决定，所以取两个高度中较小的那个。

            int area = width * h;

面积 = 宽度 × 高度。

            if(area >= res){
                res = area;
            }

如果当前面积比之前记录的最大值还大（或相等），就更新最大值。

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