---
# System prepended metadata

title: 0011. Container With Most Water (Medium)
tags: [LeetCode, Two Pointer]

---

###### tags: `LeetCode` `Two Pointer`

# 0011. Container With Most Water (Medium)
耗時： >40 分鐘 (看解答)

## 題目
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.

Notice that you may not slant the container.

## 思路
1. 一開始以為是DP題，後來理解是Two Pointer的題型，但是卡在不確定pointer移動的條件如何判斷。
2. 超過時間看解答，以下面程式碼而言，我們只需要**確保左側的高度高於右側的高度**，其他時候就是單純移動右側的位置
    * 因為當左側比右側高時，我們可以確定**移動左側不可能增加任何容量**
    * 因為此時高度受限於右側，且寬度遞減

* Time Complexity：O(n)
* Space Complexity：O(1)
   
### 程式碼
```
class Solution {
public:
    int maxArea(vector<int>& height) {
        int capacity = 0;
        int i = 0, j = height.size() - 1;
        
        while (i < j) {
            capacity = max(capacity, min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) {
                ++i;
            }
            else {
                --j;
            }
        }
        
        return capacity;
    }
};
```