盛水最多的容器
雙指針代表的是 可以作為容器邊界的所有位置的範圍。在一開始，雙指針指向數組的左右邊界，表示 數組中所有的位置都可以作為容器的邊界，因為我們還沒有進行過任何嘗試。在這之後，我們每次將 對應的數字較小的那個指針 往 另一個指針 的方向移動一個位置，就表示我們認為 這個指針不可能再作為容器的邊界了。
該題需要證明一個觀點
即如果當前的邊為兩個邊界的較大的一條邊,則無論怎麼移動改變,也不會使移動後的容量大於等於當前容量
假設x<=y 且 height[x]<=height[y],則容器內的容量最大為 height[x]*(y-x).
如果此時移動了y,由於 height[x]<=height[y] ,移動後的 height[y-1]有兩種情況,
- height[x]<=height[y-1] 此時容量為 height[x](y-1-x) < height[x](y-x)
- height[x]> height[y-1] 此時容量為 height[y-1](y-1-x), 又因為height[y-1]<height[x] ,y-1-x<y-x,所以最終的容量仍小於 height[x](y-x)
這種情況下,只有移動較小那一條邊才會有機會使得容量變大
這也叫短板效應,即決定一個木桶最大容積的不是他的最長的板子，而是他最短的板子
//給你 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i,
//ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
//
// 說明：你不能傾斜容器。
//
//
//
// 示例 1：
//
//
//
//
//輸入：[1,8,6,2,5,4,8,3,7]
//輸出：49
//解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
//
// 示例 2：
//
//
//輸入：height = [1,1]
//輸出：1
//
//
// 示例 3：
//
//
//輸入：height = [4,3,2,1,4]
//輸出：16
//
//
// 示例 4：
//
//
//輸入：height = [1,2,1]
//輸出：2
//
//
//
//
// 提示：
//
//
// n = height.length
// 2 <= n <= 3 * 104
// 0 <= height[i] <= 3 * 104
//
// Related Topics 數組 雙指針
// 👍 2235 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
/**
* 該題需要證明一個觀點
* 即如果當前的邊為兩個邊界的較大的一條邊,則無論怎麼移動改變,也不會使移動後的容量大於等於當前容量
* 假設x<=y 且 height[x]<=height[y],則容器內的容量最大為 height[x]*(y-x).
* 如果此時移動了y,由於 height[x]<=height[y] ,移動後的 height[y-1]有兩種情況,
* 1. height[x]<=height[y-1] 此時容量為 height[x]*(y-1-x) < height[x]*(y-x)
* 2. height[x]> height[y-1] 此時容量為 height[y-1]*(y-1-x), 又因為height[y-1]<height[x] ,y-1-x<y-x,所以最終的容量仍小於 height[x]*(y-x)
* 這種情況下,只有移動較小那一條邊才會有機會使得容量變大
* 這也叫短板效應
*/
class Solution {
public int maxArea(int[] height) {
int max = 0;
int highLine , lowLine;
int i = 0; int j = height.length-1;
while (i<j){
max = Math.max(max,Math.min(height[i],height[j])*(j-i));
if(height[i]<=height[j]){
i++;
}else {
j--;
}
}
return max;
}
}
//leetcode submit region end(Prohibit modification and deletion)
