您好,登錄后才能下訂單哦!
這篇文章主要講解了“如何編寫代碼實現(xiàn)盛最多水的容器”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“如何編寫代碼實現(xiàn)盛最多水的容器”吧!
難度:中等
給你 n
個非負(fù)整數(shù) a1,a2,...,an
,每個數(shù)代表坐標(biāo)中的一個點 (i, ai)
。在坐標(biāo)內(nèi)畫 n
條垂直線,垂直線 i
的兩個端點分別為 (i, ai)
和 (i, 0)
。找出其中的兩條線,使得它們與 x
軸共同構(gòu)成的容器可以容納最多的水
說明:你不能傾斜容器
輸入:[1,8,6,2,5,4,8,3,7] 輸出:49 解釋:圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下,容器能夠容納水(表示為藍(lán)色部分)的最大值為 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
如何求最多的水
求最多的水,本質(zhì)上是求兩個垂直線在二維坐標(biāo)軸上組成的面積大小,根據(jù)木桶原理,能裝多少水取決于它最短的那塊木板,設(shè)定x
,y
作為兩個線的下標(biāo),對應(yīng)height[x]
,height[y]
作為對應(yīng)xy
的高度整體最終兩個垂直線求得的面積公式為
abs(
y
-x
) * min(height[x]
,height[y]
)
通過暴力雙重FOR
循環(huán),可以很快解出此題,依次算出每個垂直線
跟其他垂直線組成的面積大小,超過當(dāng)前最大面積則替換,循環(huán)完后得出最大面積
class Solution { public int maxArea(int[] height) { // (y-x)* min(ax,ay) if(height.length <= 1) return 0; int res = 0;//保存結(jié)果 for(int i = 0; i < height.length - 1; i++)//以i為左擋板,從O開始 { for(int j = height.length - 1; j > i; j--)//以j為右擋板,從height.length - 1開始 { int L = j - i;//底邊長度 int H = Math.min(height[i], height[j]);//對短的板子為高 res = Math.max(res, L * H);//取最大值 } } return res; } }
時間復(fù)雜度 O(N^2)
你有你的雙指針,我有我的FOR循環(huán)
超時
,之前還沒有超時,現(xiàn)在提交已經(jīng)顯示超時...
我們可以設(shè)定兩個指針
來分別指定整個height
的全部,指針x
初始指定最左側(cè)
坐標(biāo),指針y
初始指定最右側(cè)
坐標(biāo)
我們需要不斷移動指針X
或者Y
,求取對應(yīng)XY
的面積,直到X
指針和Y
指針相等則面積計算結(jié)束
abs(
y
-x
) * min(height[x]
,height[y]
)
回到我們上面的面積計算公式,其中可以拆解為兩部分
abs(y
-x
)
min(height[x]
,height[y]
)
這里面有一個隱藏的條件公式
移動X,X=X+1
移動Y,Y=Y-1
對應(yīng)abs(y-x)
,無論移動X
或者Y
,對應(yīng)abs(y-x)
的值是不變的
移動X,abs(y-(x+1)) = abs(y-x-1)
移動Y,abs((y-1)-x) = abs(y-x-1)
對應(yīng)min(height[x],height[y])
如果移動height[x],height[y]中的最大值,則 min(height[x],height[y])
的值可能不變
或者變小
不變,新的最大值 > = 現(xiàn)有最小值
變小,新的最大值 < 現(xiàn)有最小值
如果移動height[x],height[y]中的最小值,則 min(height[x],height[y])
的值可能變小
,不變
或者變大
變小,新的最小值 < 現(xiàn)有最小值
不變,新的最小值 = 現(xiàn)有最小值
變大,新的最小值 > 現(xiàn)有最小值
在既有情況下,選擇變大方向是計算更大面積的唯一取法
class Solution { public int maxArea(int[] height) { //長度 int length = height.length ; //左側(cè)指針 int x = 0 ; //右側(cè)指針 int y = length - 1; //最大面積 int res = 0; while(x!=y){ //取兩個指針中最小的高度 int minHeight = Math.min(height[x],height[y]); //計算res,取最大 res = Math.max(res,(y-x)*minHeight); //如果x對應(yīng)的高度 > y對應(yīng)的高度,則需要移動高度低的指針,即y=y-1 if(height[x]-height[y] > 0){ y = y - 1; }else{ //對應(yīng)x對應(yīng)的高度 <= y對應(yīng)的高度,則需要移動高度低的指針,即x=x+1 x = x + 1; } } return res; } }
時間復(fù)雜度:O(N)
,雙指針總計最多遍歷整個數(shù)組一次
空間復(fù)雜度:O(1)
,只需要額外的常數(shù)級別的空間
感謝各位的閱讀,以上就是“如何編寫代碼實現(xiàn)盛最多水的容器”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對如何編寫代碼實現(xiàn)盛最多水的容器這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。