1.題目簡介

題目鏈接：
https://leetcode-cn.com/problems/container-with-most-water/
題目描述:
給定 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

image

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

示例:

輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49

2.解題思路

2.1.暴力解法

數(shù)組的長度為n,組成的矩形區(qū)域的面積共需要考慮n(n-1)/2種情況，在這n(n-1)/2個(gè)結(jié)果中取最大值，用雙層for循環(huán)即可解決。
這種解題思路是沒問題的，不過在leetcode上提交超時(shí)了，而且我寫的代碼也不是最簡潔的，有很多冗余的代碼
先看一下我寫的

   public static int maxArea(int[] height) {
        int t =0;
        if (height.length==2) {
            return Math.min(height[0],height[1]);
        }
        int length = height.length*(height.length-1)/2;
        int[] temp =new int[length];
        for (int i = 0; i <height.length-1 ; i++) {
            for (int j = i+1; j <height.length ; j++) {
                if (t>=length) {
                    break;
                }
                temp[t]= (j-i)*Math.min(height[j],height[i]);
                t++;
            }
        }
        Arrays.sort(temp);
        return temp[length-1];

    }

這段代碼額外引入了一個(gè)長度為n(n-1)/2的數(shù)組，為了填充temp數(shù)組，引入了一個(gè)變量t，進(jìn)行計(jì)數(shù)。在運(yùn)行測試用例的時(shí)候，也需要排除掉數(shù)組長度n=2的特殊情況。
最終需要排序取最大值。
暴力法寫的也不是最簡潔的。
看一下官方提供的暴力法的代碼:

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;
    }

官方給的代碼很簡潔，2層for循環(huán)加一個(gè)maxarea變量就解決了。

2.2.雙指針解法

矩形的面積由長和寬共同決定的，x軸為長，y軸為寬，現(xiàn)在需要求xy的最大值。由暴力解法可知共有n(n-1)/2種情況。
官方給的示例圖中，我們可以看出，面積的最大值會受較短邊的影響，即會受y軸取值大小的影響。
雙指針解法是一個(gè)指針放在最左邊，一個(gè)放在最右邊，將2個(gè)指針往內(nèi)側(cè)移動，這樣
就可以找到最大值。
那么哪個(gè)指針往內(nèi)側(cè)移呢，將值較小的指針往內(nèi)側(cè)移動，為什么要移動較小邊呢，
指針向內(nèi)側(cè)移動，x軸的長度總是會減一格，在x軸的長度必定減小的請求下，只有y軸的值變大，xy才有可能變大。
如果將較大值的指針向內(nèi)側(cè)移動，留下了較小值的指針，那么移動之后的面積肯定是減小的，如果移動較小邊的指針，還有可能遇到更大的值，這樣才能增加面積。
看一下代碼:

 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;
    }

詳細(xì)解答請看一下下方給出的官方題解鏈接
寫的很清晰
https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode/