給定一個長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。找出其中的兩條線使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。返回容器可以儲存的最大水量。說明你不能傾斜容器。分析求最大水量就是求最大容積長方形的面積很容易得出是長乘寬Si長*k寬i是兩個點之間的距離k是兩條長邊最短的那條邊因為水箱容器所能儲存的水肯定是和短邊齊平的暴力算法 首先先嘗試最簡單思路就是雙重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};可以看到大部分案例都通過了證明邏輯上可行但是還有幾個沒通過。查看沒通過的案例可以直接看出是因為案例數(shù)組太到雙重for循環(huán)的時間規(guī)模是n2所以運行超時了。雙指針法 想辦法把雙重for循環(huán)降為單層for循環(huán)因為遍歷數(shù)組是我們肯定要做的事情不做就沒辦法得到具體的高度了。設(shè)置雙指針i,j,i代表數(shù)組開頭j代表數(shù)組末尾雙指針一個頭一個尾開始計算最大水箱值。左指針i在最左端右指針j在最右端。每次計算當(dāng)前面積然后移動高度更小的那一側(cè)指針如果height[i] height[j]移動左指針i解釋當(dāng)前 是短板。如果移動右指針寬度一定會變小而容器高度最高只能是 height [i]面積只會更小沒有必要。所以只能移動短板才有可能得到更大高度獲得更大面積。如果height[j] height[i]移動右指針j--長板向內(nèi)收縮不會帶來收益短板向內(nèi)收縮才有機會提升容器高度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; } };