給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。找出其中的兩條線使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。返回容器可以儲(chǔ)存的最大水量。說(shuō)明你不能傾斜容器。分析求最大水量就是求最大容積長(zhǎng)方形的面積很容易得出是長(zhǎng)乘寬Si長(zhǎng)*k寬i是兩個(gè)點(diǎn)之間的距離k是兩條長(zhǎng)邊最短的那條邊因?yàn)樗淙萜魉軆?chǔ)存的水肯定是和短邊齊平的暴力算法 首先先嘗試最簡(jiǎn)單思路就是雙重for循環(huán)遍歷求最大值class Solution { 2public: 3 int maxArea(vectorint height) { 4 int sum0; 5 for(int i0;iheight.size();i) 6 { 7 for(int j0;jheight.size();j) 8 { 9 int xj-i; 10 int ymin(height[j]-height[i]); 11 if( x*ysum) 12 { 13 sum x*y; 14 } 15 16 17 } 18 } 19 return sum; 20 } 21};可以看到大部分案例都通過(guò)了證明邏輯上可行但是還有幾個(gè)沒(méi)通過(guò)。查看沒(méi)通過(guò)的案例可以直接看出是因?yàn)榘咐龜?shù)組太到雙重for循環(huán)的時(shí)間規(guī)模是n2所以運(yùn)行超時(shí)了。雙指針?lè)?想辦法把雙重for循環(huán)降為單層for循環(huán)因?yàn)楸闅v數(shù)組是我們肯定要做的事情不做就沒(méi)辦法得到具體的高度了。設(shè)置雙指針i,j,i代表數(shù)組開(kāi)頭j代表數(shù)組末尾雙指針一個(gè)頭一個(gè)尾開(kāi)始計(jì)算最大水箱值。左指針i在最左端右指針j在最右端。每次計(jì)算當(dāng)前面積然后移動(dòng)高度更小的那一側(cè)指針如果height[i] height[j]移動(dòng)左指針i解釋當(dāng)前 是短板。如果移動(dòng)右指針寬度一定會(huì)變小而容器高度最高只能是 height [i]面積只會(huì)更小沒(méi)有必要。所以只能移動(dòng)短板才有可能得到更大高度獲得更大面積。如果height[j] height[i]移動(dòng)右指針j--長(zhǎng)板向內(nèi)收縮不會(huì)帶來(lái)收益短板向內(nèi)收縮才有機(jī)會(huì)提升容器高度class Solution { public: int maxArea(vectorint height) { int sum0; int i0; int jheight.size()-1; while(ij) { int xj-i; int y min(height[i],height[j]); if(x*ysum) { sumx*y; } if(height[i]height[j]) { i; } else { j--; } } return sum; } };