題目
給定一個長度為n的整型數(shù)組height,有n條垂線，第i條線的兩個端點(diǎn)是(i,0),(i,height(i)),找出其中的兩條線，使得他們與x軸共同構(gòu)成的容器可以容納最多的水。返回容器可以存儲的最大水量。

示例圖.png

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

分析

1. 最大水量由寬高乘積決定，假設(shè)我們找到了其中的兩條線，他們的寬高乘積最大，那么寬是兩個元素下標(biāo)差值max(i,j)-min(i,j),高是max(m,n) - min(m.n)，所以整個過程有兩步，第一步計(jì)算乘積，第二步，比較乘積大小。
2. 那么第一步計(jì)算乘積如何進(jìn)行了，這一步是最關(guān)鍵的一步，當(dāng)然比較大小也可以放到計(jì)算乘積過程中，我們只需要在每一次計(jì)算水量乘積的時候取最大值即可。
   計(jì)算乘積，需要選擇兩個點(diǎn)，簡單的思路是遍歷枚舉，但是此方法復(fù)雜度過高，那有沒有什么方法能過濾掉其中的一部分沒用的枚舉呢？
   這時我們思考，乘積最大，那就是高最大，寬最大，于是我們需要找到最大的高對應(yīng)點(diǎn)，從此點(diǎn)對應(yīng)的下標(biāo)開始找到最大的寬。但是我們尋找最大高，時間復(fù)雜度已經(jīng)是O(N),如果還有后續(xù)的遍歷時間復(fù)雜度會大于O(N)，從這點(diǎn)上考慮已經(jīng)不適合了，于是考慮換思路。假設(shè)我們還是從第一個位置開始遍歷，由于需要確定水量，必須要直到另外一個點(diǎn)的位置，那如何選擇第二個點(diǎn)的位置呢？如果能想到這一點(diǎn)，就很接近最優(yōu)解了。
   按照我們的假設(shè)，選中第一個點(diǎn)如果從第二個點(diǎn)開始選依次遍歷那么又回到了我們開始的思想-枚舉，也就是一一枚舉，復(fù)雜度毋庸置疑是很高的，那么又如何選擇第二個點(diǎn)呢？
   那我們考慮一下從第二個點(diǎn)開始選擇一直往后，所有點(diǎn)的選擇幾乎是一樣的，除了最后一個點(diǎn)，為什么說是一樣的，那是因?yàn)槲覀兗纫杜e前面的點(diǎn)，又要枚舉后面的點(diǎn)，勢必增加了復(fù)雜度，可是如果我們選擇最后一個點(diǎn)，那么問題就簡單多了，我們只需要考慮從最后一個點(diǎn)往前枚舉；至此我們確定了點(diǎn)的選擇順序。這是一個怎樣的順序呢？我們換一種描述方式：
   由于需要確定水量，我們需要界定左邊的點(diǎn)的位置和右邊的點(diǎn)的位置，我們從數(shù)組的邊界開始，依次遍歷，那么在這個過程中，會有一個什么樣的現(xiàn)象？需要不斷的觀察，左邊的點(diǎn)可以移動，右邊的點(diǎn)也可以移動，那如何移動，有什么規(guī)律嗎？為了便于分析我們來模擬一下這個過程：
   第一次，左右兩邊邊界對應(yīng)的水量為min(1,7) * (x2-x1) = 1 * 8 = 8
   假設(shè)我們移動左邊點(diǎn)，此時對應(yīng)的水量為：min(8,7) * (x2- x1) = 7 * 7 = 49
   假設(shè)我們移動右邊點(diǎn)，此時對應(yīng)的水量為：min(1,3) * 7 = 7，很顯然，一個面積變小，一個面積變大，有規(guī)律嗎？
   那我們看一下其中的變量，首先寬肯定是變小了,那么水量一定會變小嗎，很顯然不一定，因?yàn)楦呖赡茏兇螅俏覀兊哪康氖鞘裁?？是找出最大水量，那么變小的可能性我們是不是需要排除掉？是的，那為什么移動右邊的點(diǎn)水量會變小呢，因?yàn)橥葘捪拢覀円苿佑疫咟c(diǎn)得到的高變小了，也就是min(1,3,7)取最小值還是1，那可能就是這個較小的左邊值影響了整個的水量，于是我們需要考慮移除掉，
   此時規(guī)律變成了：每次我們需要移動點(diǎn)位時，需要移除較小值高的點(diǎn)，大致時這樣一個過程，因?yàn)槿绻苿虞^大值高的點(diǎn)，整個水量會變得比原來還小，這不是我們期望的。
   有了這樣的思路，我們可以開始實(shí)現(xiàn)：

func maxArea(height []int) int {
    var area int
        // 定義左右點(diǎn)位
    left, right := 0, len(height)-1
        // 開始遍歷循環(huán)，直到兩個點(diǎn)重合，循環(huán)結(jié)束，
    for left != right {
        var a1 int
        if height[left] <= height[right] {
            a1 = (right - left) * height[left]
            left++
        } else {
            a1 = (right - left) * height[right]
            right--
        }
                // 將當(dāng)前水量和上一次水量比較
        area = max(a1, area)
    }
    return area
}

提交測試：

62/62 cases passed (58 ms)
Your runtime beats 46.88 % of golang submissions
Your memory usage beats 88.54 % of golang submissions (7.5 MB)

通過！
官方解題思路比較清晰，是一個雙指針問題，主要流程也是尋找其中的規(guī)律，我們截取其中一段：

雙指針代表的是 可以作為容器邊界的所有位置的范圍。在一開始，雙指針指向數(shù)組的左右邊界，表示 數(shù)組中所有的位置都可以作為容器的邊界，因?yàn)槲覀冞€沒有進(jìn)行過任何嘗試。在這之后，我們每次將 對應(yīng)的數(shù)字較小的那個指針 往 另一個指針 的方向移動一個位置，就表示我們認(rèn)為 這個指針不可能再作為容器的邊界了。

為什么對應(yīng)的數(shù)字較小的那個指針不可能再作為容器的邊界了？

在上面的分析部分，我們對這個問題有了一點(diǎn)初步的想法。這里我們定量地進(jìn)行證明。

考慮第一步，假設(shè)當(dāng)前左指針和右指針指向的數(shù)分別為 x 和 y，不失一般性，我們假設(shè) x≤y。同時，兩個指針之間的距離為 t。那么，它們組成的容器的容量為：min(x,y)?t=x?t
我們可以斷定，如果我們保持左指針的位置不變，那么無論右指針在哪里，這個容器的容量都不會超過 x?t 了。注意這里右指針只能向左移動，因?yàn)?我們考慮的是第一步，也就是 指針還指向數(shù)組的左右邊界的時候。

我們?nèi)我庀蜃笠苿佑抑羔?，指向的?shù)為 y1，兩個指針之間的距離為 t1，那么顯然有
t1<t，并且 min(x,y1)≤min(x,y)：
如果
y1≤y，那么 min(x,y)≤min(x,y)；
如果 y1>y，那么 min(x,y1)=x=min(x,y)。
因此有：
min(x,y1)?t1<min(x,y)?t

即無論我們怎么移動右指針，得到的容器的容量都小于移動前容器的容量。也就是說，這個左指針對應(yīng)的數(shù)不會作為容器的邊界了，那么我們就可以丟棄這個位置，將左指針向右移動一個位置，此時新的左指針于原先的右指針之間的左右位置，才可能會作為容器的邊界。