11.盛最多水的容器

題目

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

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

返回容器可以儲存的最大水量。

說明：你不能傾斜容器。

示例 1：

題目.png

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

示例 2：
輸入：height = [1,1]
輸出：1

提示：

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

想法

想法.png

這個圖表橫向的看作 X 軸，豎向的看作 Y 軸， X 軸就是兩個區(qū)間 j - i， Y 軸就是取個j、i中的最低點(diǎn)（對于 Y 軸中的值），然后兩個值相乘就是這道題想要的輸出

值 = min（height[i], height[j]） * （j - i)

假設(shè) i 為最左端0，j 為最右端length - 1，兩個值移動時，寬度一定會變短，以1 為階長減少；

在每個狀態(tài)下，無論長板或短板向中間收窄一格，都會導(dǎo)致水槽 底邊寬度 ?1 變短；
如果移動長的，min（height[i], height[j]）不會變小可能變大，面積可能變大；
如果移動短的，min（height[i], height[j]）不會變大可能變小，面積可能變??；

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let l = 0, r = height.length - 1;
    let maxVal = 0;
    while(l < r){//如果是相等就構(gòu)成不了面積了
        let area = Math.min(height[l], height[r]) * (r - l);
        maxVal = Math.max(maxVal, area)
        if(height[l] < height[r]){
            l ++;
        }else{
            r --;
        }
    }
    return maxVal;
};

時間 O(n)
空間 O(1)