11. Container With Most Water (使用 C 語言解題)

11. Container With Most Water

Solved

Medium

Topics

Companies

Hint

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

google 翻譯：

給定一個長度為 n 的整數數組。 繪製 n 條垂直線，第 i 條線的兩個端點為 (i, 0) 和 (i, height[i])。

求與 x 軸一起形成容器的兩條線，使得該容器包含最多的水。

返回容器可以儲存的最大水量。
請注意，您不能傾斜容器。

想法一：

for 跑一次陣列，在 for 裡面也用 for 跑一次陣列。
當 i 與 j 不相等時，選小的值再乘上 j-i 的絕對值，
一直計算完，選計算中最大的值

寫法一：

int maxArea(int* height, int heightSize) {
    int tmp, max = 0, i, j;
    for(i=0;i<heightSize; i++) { // 相當於左邊的線
        for(j=0; j<heightSize; j++) { // 相當於右邊的線
            if(i != j) { // 兩個要不相等，容器才能裝水
                // 水量 = 左邊和右邊的線選短的 * 兩條線的距離
                tmp = fmin(height[i], height[j]) * abs(i-j);
                if(tmp > max) // 取最大水量
                    max = tmp;
            }
        }
    }
    return max;
}

結果一：

跑太多重覆的迴圈了，時間超過啦...

想法二：

線分左右兩邊開頭，直到交叉之後就停止計算。
一次只能移動一條線

寫法二：

int maxArea(int* height, int heightSize) {
    int tmp, max = 0, l, b;
    int i=0; // 左邊線的起點
    int j = heightSize-1; // 右邊線的起點
    while(i < j) { // 兩條線交叉就結束比較了
        b = j-i; // 兩條線的距離
        
        // 一次只動一條線的原則
        if(height[i] < height[j]) { // 左邊線較短的話，左邊的線往右移一格
            l = height[i]; // 記下短邊的值，因為水量最高只會到短邊的高度
            i++;
        } else { // 其餘情況，右邊的線往左移一格
            l = height[j]; // 記下短邊的值，因為水量最高只會到短邊的高度
            j--;
        }
        
        // 水量 = 短邊 * 距離
        tmp = l * b;
        if(tmp > max)
            max = tmp;
    }
    return max;
}

結果二：

結果不太好，但看起來已經沒什麼好改的了...