Leetcode --- Container with Most Water(Medium)
===

## Description

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.

### Example

* #### Ex1

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

* #### Ex2

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

### Constrains

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

## Solutions

### Method 1: Brute Force

從左到右對每一條線都算能容多少water.

class Solution {
    public int maxArea(int[] height) {
        int water =0;
        for(int i =0;i<height.length;i++)
        {
            for(int j =i+1;j<height.length;j++)
            {
                int k = height[i] > height[j] ? (j-i)*height[j] : (j-i)*height[i];        
                if(k>water)
                    water =k;
            }
        }
        return water;
    }
}

**line 8:** 判斷左右哪個短,用短的計算容量,否則會溢出.

### Time Complexity

=>**O(n^2^)**

### Submissions on Leetcode

**->Submission Detail**:*Time Limit Exceeded*

時間複雜度為n^2^,而n最大可以為10^5^,不足以在限制時間內算完,固fail.

## Method 2:Two Pointer Approach

觀察判斷會bound住water的關鍵 :
* 短的會限制長的(縱軸)
* 距離才是關鍵(橫軸)

所以計算方法:從最遠的兩點開始算容量,慢慢往內夾擠,夾擠辦法為選短的.

class Solution {
    public int maxArea(int[] height) {
        int front=0;
        int tail=height.length -1;
        int water =0;
        while(front<tail)
        {
            int k =0;
            if(height[front] > height[tail])
            {
                k = (tail - front ) * height[tail];
                tail--;
            }
            else
            {
                k = (tail - front ) * height[front];
                front++;
            }
            if(k>water)
                water =k;
        }
        return water;
    }
}

### Time Complexity

=> **O(n)**

### Submissions on Leetcode

Runtime: **2 ms**, faster than **97.60%** of Java online submissions for Container With Most Water.
Memory Usage: **49.8 MB**, less than **97.06%** of Java online submissions for Container With Most Water.

###### tags: `Leetcode` `Medium` `Array`