DAY 9
0

# 11. Container With Most Water

## Question

Given `n` non-negative integers `a1`, `a2`, ..., `an` , where each represents a point at coordinate `(i, ai)`. `n` vertical lines are drawn such that the two endpoints of the line `i` is at `(i, ai)` and `(i, 0)`. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

## Example

### Example1

``````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.
``````

### Example2

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

### Example3

``````Input: height = [4,3,2,1,4]
Output: 16
``````

### Example4

``````Input: height = [1,2,1]
Output: 2
``````

### Constraints

• `n == height.length`
• `2 <= n <= 105`
• `0 <= height[i] <= 104`

## 解題

### Think

• 一開始是用兩層for loop暴力解，但是解陣列長度過長的測資時，會跑超過時間限制。
• 就稍微改寫了一下，用一層迴圈解解看，用`left``right`兩個變數指向容器左右兩側的位址，用`min`取左右兩側的低值，乘上`right-left`(寬)，最後跟目前的最大面積取`max`
• `height[left] > height[right]``right -= 1`，這是因為要讓面積變大的，就代表寬或長得比原來的大，但是因為我們從左右兩側開始內縮，我們勢必要找比較高的值，所以才會固定比較高的那側，內縮矮的那側，看能不能找到更高的值。
• 至於`height[left] == height[right]`會兩側都內縮是因為兩邊如果都一樣長，那接下來不論是縮哪側，如果遇到比較高的值，還是會因為要選矮的那側，而選到原來的值；如果遇到比較低的值，也會因為要選矮的那側，而高度變低，所以乾脆就兩側一起內縮。

### Code

#### Python

##### Brute force (Submit Failed)
``````class Solution:
def maxArea(self, height: List[int]) -> int:
x = 0
y = 0
max_contain = 0

for index1 in range(len(height)-1):
y = 0
for index2 in range(len(height)-1, 0, -1):
if y >= min(height[index1], height[index2]):
continue
else:
y = min(height[index1], height[index2])
if max_contain <= (index2-index1)*y:
max_contain = (index2-index1)*y
return max_contain
``````
##### Revised
``````class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1

max_contain = 0

while(left < right):
max_contain = max(max_contain, min(height[left], height[right])*(right-left) )

if height[left] > height[right]:
right -= 1
elif height[left] < height[right]:
left += 1
else:
right -= 1
left += 1

return max_contain
``````

#### C

``````int maxArea(int* height, int heightSize){
int left = 0;
int right = heightSize-1;
int current_contain = 0;
int max_contain = 0;

while(left < right){
current_contain = (height[left] >= height[right]? height[right]:height[left])*(right-left);
max_contain = (max_contain >= current_contain? max_contain:current_contain);
if (height[left] > height[right]){
right -= 1;
} else if (height[left] < height[right]){
left += 1;
} else {
right -= 1;
left += 1;
}
}

return max_contain;
}
``````

### Result

• Python

• C

30天 Leetcode解題之路30