[LeetCode][Medium] 11. Container With Most Water

Leetcode 網址: https://leetcode.com/problems/container-with-most-water/

題目說明:

給定 n 個非負整數的高度 (直線)，請找出這 n 個直線能形成的最大存水面積。

解題說明:

如果不管時間複雜度，暴力法就是直接枚舉出所有可能 O (n * n) 就能解決此問題，

Submit 果然如預期會 TLE，接著我們可以透過最大面積去減少不必要的計算，

原因是計算面積時， height[i] 跟 height[j] 是取最小，

例如: 假設最大面積現在是 n，

我們可以發現寬度至少要大於最大面積 n / height[i]，因此可以跳過一些不必要的計算，

藉由這個方式即可成功解決此題。

不過這個解法的 result 竟然只有贏 5.26% 的程式，

因此開始思考有沒有 O (n) or O(n log n) 解，最後發現我們可以使用二個 pointer 來解決此問題，

假設我們一開始取二個點 (最左與最右)，如果要找出比這個二個更大的面積要怎麼做?

我們可以直覺地發現要移動這二個點中比較矮的 (原因是寬度變小高度不變，那面積絕對不可能變大)，

因此透過以上想法即可得到出 O(n) 解。

程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 1. two pointer
        int maxAreaOfWater = 0, left = 0, right = height.size() - 1;
        while (right > left) {
            maxAreaOfWater = max(maxAreaOfWater, min(height[left], height[right]) * (right - left));
            if (height[left] > height[right]) right--;
            else if (height[left] < height[right]) left++;
            else left++, right--;
        }
        // 2.brute force
        /*int maxAreaOfWater = 0;
        for (int i = 0; i < height.size(); i++) {
            int minWidth = height[i] > 0 ? maxAreaOfWater / height[i] : 0;
            for (int j = i + minWidth; j < height.size(); j++) {
                int minHeight = min(height[i], height[j]);
                maxAreaOfWater = max(maxAreaOfWater, minHeight * (j - i));
            }
        }*/
        return maxAreaOfWater;
    }
};

結果

Runtime: 16 ms, faster than 95.99% of C++ online submissions for Container With Most Water.

Memory Usage: 17.8 MB, less than 47.04% of C++ online submissions for Container With Most Water.