Ⅰ.前记

最近在LeetCode碰到一个题，看着很简单的样子，总体通过率50%，写完提交居然碰到超时，没有通过，第二次又超时！这就很气愤了，于是记录下来。

Ⅱ.题目

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

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

示例:
      输入: [1,8,6,2,5,4,8,3,7]
      输出: 49

Ⅲ.自我解答

      第一次提交的代码如下，耗时五秒，超时！

class Solution {
    public int maxArea(int[] height) {
        int arraLen=height.length;
        if(arraLen<2){
            return 0;
        }
        List list=new ArrayList<>();
        for (int i = 0; i height[j]){
                    list.add(height[j]*(j-i));
                }else {
                    list.add(height[i]*(j-i));
                }
            }
        }
       return list.stream().distinct().max(Comparator.comparingInt(a -> a)).get();
    }
}

      放到idea里面调试发现导致是第17行的list.stream导致的耗时严重！主要是由于distinct()这个方法太低效了！于是又改改改，代码如下。

class Solution {
    public int maxArea(int[] height) {
        int arraLen = height.length;
        if (arraLen < 2) {
            return 0;
        }
        List list = new ArrayList<>();
        for (int i = 0; i < arraLen; i++) {
            for (int j = i + 1; j < arraLen; j++) {
                if (height[i] > height[j]) {
                    list.add(height[j] * (j - i));
                } else {
                    list.add(height[i] * (j - i));
                }
            }
        }
        Integer b=0;
        for (Integer a:list){
            if(a>b){
                b=a;
            }
        }
        return b;
    }
}

      嗯，现在应该可以了吧，提交，又是超时！这次耗时是500ms，查询原因是第8行的两层for循环导致的450ms耗时，又得优化优化了！

Ⅳ.官方参考答案

      看了官方的参考答案，才知道代码能写的如此优雅！

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

      官方的这个时间复杂度虽然一样是O(n²)，但耗时为22ms！（不知道为什么idea上面测试是22ms，而官方给出的答案却是400ms!！）
      官方还给了一个双指针的解法，此法甚妙啊！时间复杂度达到了O(n)，耗时为0.59ms！我和我的小伙伴都惊呆了！附上代码！

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

      这个双指针解法，主要思路是：要达到面积最大值，高和宽需要尽可能的大，所以指定两指针，一个放在首位，一个放在末尾，这样就达到了最大宽，高度又两个指针所在的位置的最小值确定（木桶短板效应），两个指针是怎么运动的呢？通过比较两个的高度，高度小的朝高度大的运动。只要通过一轮比较就能得到最大值了。

Ⅴ.自我总结

      通过这个题，感受到了我的弱小！看得多才能想得多，更重要的是勤思考，看到自己的不足，不要一时自满，却不知是井底之蛙而已！