LeetCode：盛最多水的容器

题目

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

审题

这道题目比较抽象，如果不结合手动绘图理解，还是比较难以读懂题目的。

将该题目转换为一道数学题，题目的大致含义是：

给出一个数组，该数组的索引是一个二维坐标的 x 轴坐标，该数组索引位置数组的具体值则为该二维坐标的 y 轴坐标，在二维坐标上找到该点后，经过该点作一条垂直于 x 轴的直线。
根据数组的元素个数 n ，一共可以作出 n 条垂直于 x 轴的直线，根据这些直线，找出这些直线中的任意两条直线所围成的最大的面积（也就是所谓的盛水最多的容器）。

补充：两条直线所围成的最大的面积和普通数学意义上的面积不同，因为这道题目中的本质是盛水，而水必须是水平的，所以在两条垂直直线中，我们必须选 y 轴坐标最小的那条为长度，作出一个正四方形。（题目中有说明，不能倾斜容器）

也就是所谓的木桶效应，一个木桶所能盛的最多的水，取决于木桶最短的那块木板。

思路

双重循环

在理解清楚本题的题意的时候，我第一时间想到的就是双重循环的解法，计算出每两条直线直接的面积取最大值，该两条直线所围成的木桶，即能够盛最多的水。

从解题思路来说，双重循环的解法完全没有问题，但是当我按照该思路写出代码并提交之后，发现返回解法时间超出。

从时间复杂度来说，双重循环的解法时间复杂度为 O(n^2) 级别的，很明显 O(n^2) 时间复杂度的解法并不能解出该题。

每条直线的最大面积

换一种思路，如果我们可以计算出每条直线理论上可以围成的最大面积，从这些面积中取最大值，就可以得到盛最多水的木桶。

对于任意一条直线来说，它与另外一条直线能够围成的最大面积有两种情况：

1、另外一条直线的 y 轴坐标大于该直线，这时当 x 轴坐标达到最大，即为该直线能够围成的最大面积。

2、另外一条直线的 y 轴坐标小于该直线，因为无法确定另外一条直线的 y 轴高度，所以无法确定这两条直线所围成的面积是否即为最大面积。

基于上面两点，我们可以先使两条直线在 x 轴上达到最大值，即一条直线在最左，一条直线在最右。因为两条直线的 y 轴高度总是相对的，即总是有一条直线的 y 轴高度大于等于另外一条直线的 y 轴高度，而对于 y 轴高度较小的那条直线而言，基于第一点推论，此时它的最大面积就已经得到了。

实现

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

结果

解答成功:
执行耗时:5 ms,击败了59.34% 的Java用户
内存消耗:51.8 MB,击败了68.37% 的Java用户