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++;
}

再次提交，順利通過