11. Container With Most Water

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Two Pointer、Greedy

一、題目

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.
Notive that you may not slant the container.

Example 1:
question_11

  • Input: height = [1,8,6,2,5,4,8,3,7]
  • Output: 49
  • Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

  • Input: height = [1,1]
  • Output: 1

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

二、分析

  • 此題用 Greedy 與 Two Pointer 的方向來思考。
    • 兩個垂直線相距愈遠且線高愈高，則兩線間可裝的水愈多。
    • 兩垂直線間可裝的水，受限於線高較低者。
    • 任兩線間(相距變小)，有任一解大於當下解，只有在有線高高於兩線線高較低者。
    • 故我們每次移動線高較低的那邊。
  • 兩線間可裝的水為：
    int calArea(vector<int>& height, int left, int right) {
    return min(height[left], height[right]) * (right - left);
}

三、解題

1. Two Pointer

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int calArea(vector<int>& height, int left, int right) {
    return min(height[left], height[right]) * (right - left);
}
int maxArea(vector<int>& height) {
    int left = 0, right = height.size()-1;
    int res = 0;
    do {
        res = max(res, calArea(height, left, right));
        if (height[left] < height[right])
            left++;
        else 
            right--;
    } while (left < right);
    return res;

}

回目錄 Catalog