[Leetcode] 11. Container With Most Water

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:

• 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