- 題目：11. 盛最多水的容器
- 難度：中等
- 分類：數(shù)組
- 解決方案：雙指針
今天我們學(xué)習(xí)第11題盛最多水的容器渠缕，這是一個數(shù)組的中等題轧坎，這個題目難度不大，記得在秋招面試中遇見過颜曾。下面我們看看這道題的題目描述纠拔。
題目描述
給定n個非負(fù)整數(shù)a1，a2泛豪，...稠诲，an，每個數(shù)代表坐標(biāo)中的一個點(i, ai)诡曙。在坐標(biāo)內(nèi)畫n條垂直線臀叙，垂直線i的兩個端點分別為(i, ai)和(i, 0)。找出其中的兩條線价卤，使得它們與x軸共同構(gòu)成的容器可以容納最多的水劝萤。
說明：你不能傾斜容器，且n的值至少為 2慎璧。
題目示意圖
圖中垂直線代表輸入數(shù)組[1,8,6,2,5,4,8,3,7]床嫌。在此情況下跨释，容器能夠容納水（表示為藍色部分）的最大值為 49。
分析
結(jié)合這個題目通過給出的示意圖來理解比較容易厌处，輸入數(shù)組中的數(shù)據(jù)代表水池的高度鳖谈，數(shù)組中數(shù)據(jù)之間距離表示水池的寬度，它們的乘積則為可以容納的水（即面積）阔涉。我們可以使用雙指針來解決此問題缆娃，左指針為數(shù)組起始位置，右指針為數(shù)組終止位置瑰排，然后計算此時左右指針包含的面積（注意贯要，計算面積時的高度為左右指針指向的數(shù)據(jù)取較小的那一個），然后移動指針椭住，移動規(guī)則為移動指針指向數(shù)據(jù)較小的指針（左指針向右移動崇渗，右指針向左移動）。當(dāng)左右指針指向同一個數(shù)據(jù)時函荣，則退出循環(huán)显押，最大的面積即為所求的值。
java代碼如下所示：
class Solution {
public int maxArea(int[] height) {
// res為所求面積傻挂，初始化為0乘碑， left為左指針， right為右指針
int res = 0, left = 0, right = height.length-1;
while(left < right){
// 保留最大面積
res = Math.max(res, Math.min(height[left], height[right]) * (right-left));
// 比較左右指針指向的數(shù)據(jù)金拒，移動較小數(shù)據(jù)的指針
if(height[left]<height[right])
++left; // 左指針向右移動
else
--right; // 右指針向左移動
}
return res;
}
}
圖2.提交結(jié)果
Github地址
參考鏈接
更多文章兽肤，請掃描二維碼關(guān)注『算法半島』
