如何編寫代碼實現盛最多水的容器

這篇文章主要講解了“如何編寫代碼實現盛最多水的容器”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何編寫代碼實現盛最多水的容器”吧！

題目

盛最多水的容器

描述

難度：中等

給你 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水

說明：你不能傾斜容器

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49 
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 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

Solution

暴力解法

解題思路

如何求最多的水

求最多的水，本質上是求兩個垂直線在二維坐標軸上組成的面積大小，根據木桶原理，能裝多少水取決于它最短的那塊木板，設定x，y作為兩個線的下標，對應height[x]，height[y]作為對應xy的高度整體最終兩個垂直線求得的面積公式為

abs(y-x) * min(height[x],height[y])

通過暴力雙重FOR循環，可以很快解出此題，依次算出每個垂直線跟其他垂直線組成的面積大小，超過當前最大面積則替換，循環完后得出最大面積

CODE

class Solution {
    public int maxArea(int[] height) {
        //  (y-x)* min(ax,ay)
        if(height.length <= 1) return 0;
        int res = 0;//保存結果
        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;
    }
}

復雜度

• 時間復雜度 O(N^2) 你有你的雙指針，我有我的FOR循環

結果

• 超時，之前還沒有超時，現在提交已經顯示超時...

雙指針

解題思路

我們可以設定兩個指針來分別指定整個height的全部，指針x初始指定最左側坐標，指針y初始指定最右側坐標

我們需要不斷移動指針X或者Y，求取對應XY的面積，直到X指針和Y指針相等則面積計算結束

abs(y-x) * min(height[x],height[y])

回到我們上面的面積計算公式，其中可以拆解為兩部分

• abs(y-x)

• min(height[x],height[y])

這里面有一個隱藏的條件公式

• 移動X，X=X+1

• 移動Y，Y=Y-1

對應abs(y-x)，無論移動X或者Y，對應abs(y-x)的值是不變的

• 移動X，abs(y-(x+1)) = abs(y-x-1)

• 移動Y，abs((y-1)-x) = abs(y-x-1)

對應min(height[x],height[y])

• 如果移動height[x],height[y]中的最大值，則 min(height[x],height[y])的值可能不變或者變小

• 不變，新的最大值 > = 現有最小值

• 變小，新的最大值 < 現有最小值

• 如果移動height[x],height[y]中的最小值，則 min(height[x],height[y])的值可能變小，不變或者變大

• 變小，新的最小值 < 現有最小值

• 不變，新的最小值 = 現有最小值

• 變大，新的最小值 > 現有最小值

在既有情況下，選擇變大方向是計算更大面積的唯一取法

CODE

class Solution {
    public int maxArea(int[] height) {
      	//長度
        int length = height.length ;
      	//左側指針
        int x = 0 ;
        //右側指針
        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對應的高度，則需要移動高度低的指針，即y=y-1
            if(height[x]-height[y] > 0){
                y = y - 1;
            }else{
              //對應x對應的高度 <= y對應的高度，則需要移動高度低的指針，即x=x+1
                x = x + 1;
            }
        }
        return res;
    }
}

復雜度

• 時間復雜度：O(N)，雙指針總計最多遍歷整個數組一次

• 空間復雜度：O(1)，只需要額外的常數級別的空間

感謝各位的閱讀，以上就是“如何編寫代碼實現盛最多水的容器”的內容了，經過本文的學習后，相信大家對如何編寫代碼實現盛最多水的容器這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！