當(dāng)前位置:首頁(yè) > IT技術(shù) > 編程語(yǔ)言 > 正文

leecode算法-11盛最多水的容器
2022-03-06 18:06:45

題目來(lái)源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/container-with-most-water

給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組?height?。有?n?條垂線,第 i 條線的兩個(gè)端點(diǎn)是?(i, 0)?和?(i, height[i])?。

找出其中的兩條線,使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。

返回容器可以儲(chǔ)存的最大水量。

說(shuō)明:你不能傾斜容器。

輸入:[1,8,6,2,5,4,8,3,7]
輸出:49 
解釋:圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下,容器能夠容納水(表示為藍(lán)色部分)的最大值為?49。
輸入:height = [1,1]
輸出:1

開始解答:
解讀題目的訴求,就是求最大的面積,可以理解程高度是 heign[n], 寬度為(n-i)數(shù)組之間距離的最大面積。這時(shí)我想到最簡(jiǎn)單的做法就是2層for循環(huán)去解決。示例如下:

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = 0; j < height.length; j++) {
            if (i == j) {
                continue;
            }
            int low = Math.min(height[i], height[j]);
            int width = j - i;
            max = Math.max(low * width, max);
        }
    }
    return max;
}

本地測(cè)試下,沒有問題,準(zhǔn)備提交,
結(jié)果是超出時(shí)間限制,看來(lái)還得想辦法優(yōu)化下。
重新回到題目,兩次for循環(huán)是這樣的,一個(gè)值固定不動(dòng),變另一個(gè)值,遍歷所有的情況,執(zhí)行的時(shí)間復(fù)雜度是 O(n2),執(zhí)行效率低,所以我們想辦法把復(fù)雜度降低。
所以我們可以同時(shí)改邊兩個(gè)值,從height[0]heignt[n-1]向內(nèi)逼近。
即比較heignt[0]heignt[n-1]向內(nèi)移動(dòng),移動(dòng)的規(guī)則為 那個(gè)值小,改變那個(gè)值。這樣 就有了第二版代碼,如下:

public int maxArea2(int[] height) {
    int max = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int low = Math.min(height[i], height[j]);
        max = Math.max(low * (j - i), max);
        if (height[i] > height[j]) {
            j--;
        } else {
            i++;
        }
    }
    return max;
}

剛剛提到的那個(gè)值小移動(dòng)那個(gè)就是這個(gè)

if (height[i] > height[j]) {
    j--;
} else {
    i++;
}

再次提交,順利通過

本文摘自 :https://www.cnblogs.com/

開通會(huì)員,享受整站包年服務(wù)立即開通 >