一、题目描述

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

二、解题

解题思路在源码中很详细标明

三、源码

  /**
     * 简言之，这个算法是计算最大面积
     * 暴力法：把所有可能列举出来做比较
     * <p>
     * 执行用时 450 ms在所有 Java 提交中击败了16.95%的用户
     * 内存消耗 :39.9 MB, 在所有 Java 提交中击败了36.43%的用户
     */

    public int maxArea(int[] height) {
        int lenght = height.length;
        int result = 0;
        for (int i = 0; i < lenght; i++) {
            for (int j = i; j < lenght; j++) {
                int min = Math.min(height[i], height[j]);
                result = Math.max(result, min * (j - i));
            }
        }
        System.out.println(result);
        return result;
    }

    /**
     * 双指针法：
     * <p>
     * 执行用时 3 ms在所有 Java 提交中击败了92.82%的用户
     * 内存消耗 :40.3 MB, 在所有 Java 提交中击败了7.86%的用户
     *
     *         一次遍历就可以，所以比较一次就要把当前这根柱子最大的面积获取。
     *         假设第一根柱子(a1)，当然是与比他高且最远(an)的那根面积最大。
     *         所以当a1<a你的时候，a1与之搭配的面积最大，再和其他面积做对比。
     *         如果a1>an,就让an往前移一点，也是第一种思路，只是换了个方向。
     * 这道题是参考网友的解法，实在是nb ，
     */

    public int maxArea2(int[] height) {
        int lenght = height.length;
        int result = 0, i = 0, j = lenght - 1;
        while (i < j) {
            if (height[i] < height[j]) {
                System.out.println("height[j]:" + (height[j]) + " height[i]:" + height[i] + " width:" + (j - i) + " result:" + result);
                result = Math.max(result, height[i] * (j - i));
                i++;
            } else {
                System.out.println("height[i]:" + (height[i]) + " height[j]:" + height[j] + " width:" + (j - i) + " result:" + result);
                result = Math.max(result, height[j] * (j - i));
                j--;
            }
        }
        System.out.println(result);
        return result;
    }    /**
     * 简言之，这个算法是计算最大面积
     * 暴力法：把所有可能列举出来做比较
     * <p>
     * 执行用时 450 ms在所有 Java 提交中击败了16.95%的用户
     * 内存消耗 :39.9 MB, 在所有 Java 提交中击败了36.43%的用户
     */

    public int maxArea(int[] height) {
        int lenght = height.length;
        int count = 0;
        int result = 0;
        for (int i = 0; i < lenght; i++) {
            for (int j = i; j < lenght; j++) {
                int min = Math.min(height[i], height[j]);
                result = Math.max(result, min * (j - i));
                ++count;
            }
        }
        System.out.println("maxArea:执行了"+count+"遍，result = "+result);
        return result;
    }

    /**
     * 双指针法：
     * <p>
     * 执行用时 3 ms在所有 Java 提交中击败了92.82%的用户
     * 内存消耗 :40.3 MB, 在所有 Java 提交中击败了7.86%的用户
     *
     *         一次遍历就可以，所以比较一次就要把当前这根柱子最大的面积获取。
     *         假设第一根柱子(a1)，当然是与比他高且最远(an)的那根面积最大。
     *         所以当a1<a你的时候，a1与之搭配的面积最大，再和其他面积做对比。
     *         如果a1>an,就让an往前移一点，也是第一种思路，只是换了个方向。
     * 这道题是参考网友的解法，实在是nb ，
     */

    public int maxArea2(int[] height) {
        int lenght = height.length;
        int result = 0, i = 0, j = lenght - 1,count = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                result = Math.max(result, height[i] * (j - i));
                i++;
            } else {
                result = Math.max(result, height[j] * (j - i));
                j--;
            }
            ++count;
        }
        System.out.println("maxArea2:执行了"+count+"遍，result = "+result);
        return result;
    }

四、附上github

https://github.com/maryyMa/LeetCodeTest/commit/aa7fca7d7bf6c9c1f34fa190484335c6fdba874b

五、总结：

maxArea:执行了45遍，result = 49
maxArea2:执行了8遍，result = 49

这也难怪用双指针法只要3ms就能搞定了。算法的魅力就是在于做一道题有很多种解法，但我们一直在追求最优解。不过双指针占内存比较大，目前没有想法去优化，先记小本本，说不定哪天就突然顿悟了呢