題目網址：https://leetcode.cn/problems/container-with-most-water/

題意：給一整數 array height 和一整數 n。有 n 條線其高度為 height[i], 找出其中的兩條線，使得它們與 x 軸組成的容器可以容納最多的水。

Solution：

想法：利用 Two Pointers

  • 當前 area = 兩條線中較短的高度 * 彼此間的距離
  • 移動較短那端的 ptr, 盡量保留較長的線

為何是移動較短那端的 ptr？ 因為 area 是用下限計算的, 我們希望下限越高越好, 但是下限會受限於上限 ➔ 因此我們採取的策略為「維持上限、提升下限」

e.g. height = [1, 3, 5, 7]

  • 最一開始 left = 0, right = 3 ➔ nums[left] = 1, nums[right] = 7
    此時 area = min(1, 7) * (3 - 0) = 1 * 3 = 3

    • 若移動 right : left = 0, right = 2 ➔ nums[left] = 1, nums[right] = 5
      此時 area = min(1, 5) * (2 - 0) = 1 * 2 = 2 反而更小了

    • 若移動 left : left = 1, right = 3 ➔ nums[left] = 3, nums[right] = 7
      此時 area = min(3, 7) * (3 - 1) = 3 * 2 = 6

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, left = 0, right = height.size() - 1;

        while (left < right)  {
            const int area = min(height[left], height[right]) * (right - left);
            res = max(res, area);

            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }
        }
        return res;
    }
};
  • time：$O(n)$ ➔ while loop 遍歷 height
  • space：$O(1)$ ➔ 只需常數空間