大家好 我是“@不會飛的小飛驢”
4 盛最多水的容器
給你 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，
首先 大家想到的是什么解決方法，歡迎大家在下方評論，
整體思路：這道題主要用到思路是：縮減搜索空間
程式：
public int maxArea(int[] height) {
int res = 0;
int i = 0;
int j = height.length - 1;
while (i < j) {
int area = (j - i) * Math.min(height[i], height[j]);
res = Math.max(res, area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
看了答案知道了演算法雙指標解法，總感覺怪怪的，為什么指標直接向中間移動時，感覺漏掉了好多種情況？（不知道大家有沒有這種感覺，在有些情況的時候總感覺漏了一些什么，但是結果是對的），
原理：用一句話概括雙指標解法的要點：指標每一次移動，都意味著排除掉了一個柱子，
如下圖所示，在一開始，我們考慮相距最遠的兩個柱子所能容納水的面積，水的寬度是兩根柱子之間的距離 d = 8；水的高度取決于兩根柱子之間較短的那個，即左邊柱子的高度 h = 3，水的面積為3×8=24，
如果選擇固定一根柱子，另外一根變化，水的面積會有什么變化嗎？思考一下：
a當前柱子是最兩側的柱子，水的寬度 d 為最大，其他的組合，水的寬度都比這個小，
b左邊柱子較短，決定了水的高度為 3，如果移動左邊的柱子，新的水面高度不確定，一定不會超過右邊的柱子高度 7，
c如果移動右邊的柱子，新的水面高度一定不會超過左邊的柱子高度 3，也就是不會超過現在的水面高度，
所以，如果固定左邊的柱子，移動右邊的柱子，那么水的高度一定不會增加，且寬度一定減少，所以水的面積一定減少，這個時候，左邊的柱子和任意一個其他柱子的組合，其實都可以排除了，也就是我們可以排除掉左邊的柱子了，
這個排除掉左邊柱子的操作，就是雙指標代碼里的 i++，i 和 j 兩個指標中間的區域都是還未排除掉的區域，隨著不斷的排除，i 和 j 都會往中間移動，當 i 和 j 相遇，演算法就結束了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257871.html
標籤：其他