11. Container With Most Water

• Hardness: $$\color{orange}\textsf{Medium}$$
• Ralated Topics: ArrayTwo PointerGreedy

### 一、題目#

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

### 二、分析#

• 此題用 GreedyTwo 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;

}