【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ō)明：你不能傾斜容器榴嗅，且 n 的值至少為 2。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]陶舞。在此情況下嗽测，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
思路：
（1）計(jì)算面積最大值的初值肿孵，該初值以數(shù)組中的第一個(gè)元素和最后一個(gè)元素構(gòu)成兩邊唠粥。
（2）設(shè)置首尾兩個(gè)指針疏魏，首指針i指向數(shù)組中的第一個(gè)元素，尾指針j指向數(shù)組中的最后一個(gè)元素晤愧。
（3）當(dāng)首指針i小于尾指針j時(shí)大莫，一直循環(huán)計(jì)算其面積。若計(jì)算所得的當(dāng)前面積大于（1）步驟中所計(jì)算得的面積最大值养涮，則更新最大值葵硕。每一次循環(huán)都舍棄索引i和索引j中較短的那一條邊。
為什么每一次循環(huán)舍棄索引i和索引j中較短的那一條邊贯吓，我們最終得到的結(jié)果就會(huì)是最大的面積值呢？
反證法：
假設(shè)我們現(xiàn)在遍歷到了height數(shù)組中第i和第j個(gè)元素蜀变，且height[i] < height[j]悄谐，如果我們的面積最大值中取了第i個(gè)元素，那么構(gòu)成我們的面積最大值的兩個(gè)元素一定是i和j库北，因?yàn)閖繼續(xù)減小的話長(zhǎng)方形的寬肯定一直在減小爬舰，而其高最多只能是height[i]，不可能比height[i]更大寒瓦，因此我們?cè)诶^續(xù)遍歷的過(guò)程中情屹，繼續(xù)保持i不變而減小j是沒有意義的。我們可以直接舍棄i杂腰，從i + 1開始去繼續(xù)遍歷垃你。
由于整個(gè)過(guò)程只遍歷了一次數(shù)組，因此時(shí)間復(fù)雜度為O(n)喂很，其中n為數(shù)組height的長(zhǎng)度惜颇。而使用空間就是幾個(gè)變量，故空間復(fù)雜度是O(1)
java代碼：
public class Solution {
public int maxArea(int[] height) {
int n = height.length;
int i = 0;
int j = n - 1;
int area = (n - 1) * Math.min(height[i], height[j]);
while(i < j) {
area = Math.max(area, (j - i) * Math.min(height[i], height[j]));
if(height[i] < height[j]) {
i++;
}else {
j--;
}
}
return area;
}
}
