文章收錄于LeetCode專欄

---

盛最多水的容器

??給你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)成的容器可以容納最多的水。

??說(shuō)明：你不能傾斜容器。

??示例 1：

輸入：[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ù)組中各個(gè)元素表示柱子的高度（坐標(biāo)系中的縱坐標(biāo)），這里的高度就可以作為容器的高，兩跟柱子之間的間距就作為容器的長(zhǎng)，即容器最多容納水就是高乘以長(zhǎng)。要把柱子的高作為容器的高，就會(huì)必須得取二則的相對(duì)矮的那一根柱子。例如1和8之間就得取1。

2、列出所有解

??通過(guò)對(duì)題意的理解可以使用暴力法和左右收斂法來(lái)解答改題目。

解法一（暴力法）

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

解法二（左右收斂）

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

3、復(fù)雜度分析

??首先來(lái)看下暴力解法的時(shí)間復(fù)雜度和空間復(fù)雜度，因?yàn)楸┝Ψㄊ褂昧藘蓪友h(huán)，所以時(shí)間復(fù)雜度為O(n²)，沒(méi)有使用任何額外空間，所以空間復(fù)雜度為O(1)。左右收斂法因?yàn)橹皇褂靡粚友h(huán)，所以時(shí)間復(fù)雜度為O(n)，同樣空間復(fù)雜度為O(1)。綜上左右收斂法是最優(yōu)解。

---

一鍵三連，讓我的信心像氣球一樣膨脹！