一、題目

給定一個(gè)長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。

找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水，返回容器可以儲存的最大水量。

說明：你不能傾斜容器。

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【輸入】height = [1,1]
【輸出】1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

三、解題思路

3.1> 思路1：雙向指針

通過題意，我們會接收到一個(gè)整數(shù)數(shù)組height，它里面有n個(gè)數(shù)值，代表木樁的高度。任意兩個(gè)木樁都可以與x軸組成一個(gè)容器水槽，那么哪個(gè)組合的水槽可以容納更多的水呢？其實(shí)這道題里面有兩個(gè)因素是盛水容量的關(guān)鍵點(diǎn)：一個(gè)是水槽x軸的長度，另一個(gè)就是兩個(gè)木樁中最短的木樁高度。這兩個(gè)值的乘積就是盛水容量的大小了。

那么雙向指針的解法就是創(chuàng)建兩個(gè)指針——head頭指針和tail尾指針。最初head指向height數(shù)組中index=0的位置，tail指向height數(shù)組中index=height-1的位置。那么此時(shí)情況假設(shè)我們?nèi)缦聢D所示，height[head]是小于height[tail]的，head指針與tail的指針長度為x（即：tail - head = height - 1 - 0），那么此時(shí)水槽可以承載的水容量就等于：height[head] * x。如下圖所示：

那么根據(jù)雙指針?biāo)惴?，我們需要讓head指針或者tail指針向彼此靠攏，那么移動哪一個(gè)指針的？我們會根據(jù)對比兩個(gè)木樁的高度，去移動那個(gè)更短的。比如，head指針指向的木樁較短，那么我們將head指針向右移動。但是如果是tail指針指向的木樁較短，那么我們就將tail指針向左移動。當(dāng)兩個(gè)指針在某個(gè)位置相遇，則結(jié)束整個(gè)過程。

那么有同學(xué)會問，為什么要這么對比呢？這道題，我們一般來說，第一反應(yīng)應(yīng)該是兩層for循環(huán)，即，先鎖定第一個(gè)木樁，然后去依次對比其他的木樁，每次計(jì)算容量，通過Math的max函數(shù)，只記錄最大容量的。然后我們再鎖定第二個(gè)木樁，再去對比其他的木樁（非第一個(gè)木樁），然后一次類推。這種方式是沒錯(cuò)的，但是屬于暴力破解的范疇了。那么，雙向指針能保證計(jì)算的正確性嗎？

我們還是以上面圖為例，由于最初的head指向的木樁高度為height[0]，tail指向的木樁高度為height[height.length - 1]，他們之間的距離為x，由于height[0] 小于 height[height.length - 1]，所以容器的盛水容量就是 height[0] * x，這里的x已經(jīng)是最大值的，也就是說，無論head指針和tail指針怎么移動，兩個(gè)指針之間的距離都不會大于x。那么其實(shí)我們就相當(dāng)于“鎖定”了最大容器底部x了，而每次無論移動head指針還是tail指針，對于容器底部x的影響，都是一直在減小的，那么它的變化是一個(gè)恒定減小的趨勢。而在容器高度方面，確是一個(gè)變化的，因?yàn)槲覀儾⒉恢赖降资莌ead指向的木樁高，還是tail指向的木樁高。

那么此時(shí)，我們第二個(gè)問題就是，怎么移動木樁呢？為什么要移動較短的呢？通過上面我們得出的公式height[head] * x（前提是head的木樁高度小于tail的木樁高度），那么假設(shè)我們移動更高的木樁——即tail指針，那么容器底部為：x - 1，由于沒有移動較短的木樁height[head]，所以無論tail指針全新指向的木樁高度是多高，總的容量高度都不會超過height[head]的高度，那么最大可能性容量就是：height[head] * (x - 1)；那么此時(shí)如果我們移動更矮的木樁——即head指針，那么容器底部為：x - 1，由于沒有移動較高的木樁height[tail]，所以無論head指針全新指向的木樁高度是多高，總的容量高度都不會超過height[tail]的高度，那么最大可能性容量就是：height[tail] * (x - 1)；那么由于head < tail，所以自然就得出了height[head] * (x - 1) <height[tail] * (x - 1)的結(jié)論。而本題是要獲取最大盛水容量，所以，自然就要移動較矮的木樁了。具體如下圖所示：

那么上面我們介紹了如何去計(jì)算最大盛水容量，下面就以題目中的第一個(gè)示例1為例，通過每一步驟執(zhí)行的圖解方式，完整的展現(xiàn)一次執(zhí)行的全過程。那么示例1中，height數(shù)組中的元素為[1,8,6,2,5,4,8,3,7]，我們依次通過移動head指針或者tail指針，并且計(jì)算出每次的“最大容量” ，并通過Math的max函數(shù)，將最終的最大容量作為結(jié)果進(jìn)行返回。下面是具體的8個(gè)執(zhí)行步驟，如下所示：

四、代碼實(shí)現(xiàn)

4.1> 實(shí)現(xiàn)1：雙向指針

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

今天的文章內(nèi)容就這些了：

寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ (^o)/ ~ 「干貨分享，每天更新」

題目來源：力扣（LeetCode）