題目

盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

公眾號 《java編程手記》記錄JAVA學(xué)習(xí)日常，分享學(xué)習(xí)路上點點滴滴，從入門到放棄，歡迎關(guā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)成的容器可以容納最多的水

說明：你不能傾斜容器

img

輸入：[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

Solution

暴力解法

解題思路

如何求最多的水

求最多的水，本質(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)完后得出最大面積

CODE

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ù)雜度

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

結(jié)果

• 超時，之前還沒有超時，現(xiàn)在提交已經(jīng)顯示超時...

雙指針

解題思路

我們可以設(shè)定兩個指針來分別指定整個height的全部，指針x初始指定最左側(cè)坐標(biāo)，指針y初始指定最右側(cè)坐標(biāo)

image-20210419224605310

我們需要不斷移動指針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)有最小值

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

CODE

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ù)雜度

• 時間復(fù)雜度：O(N)，雙指針總計最多遍歷整個數(shù)組一次
• 空間復(fù)雜度：O(1)，只需要額外的常數(shù)級別的空間

結(jié)果

• 執(zhí)行用時：5 ms, 在所有 Java 提交中擊敗了46.01%的用戶

• 內(nèi)存消耗：51.9 MB, 在所有 Java 提交中擊敗了26.93%的用戶

斷劍重鑄之刃，騎士歸來之時