大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題Day~

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

  • 

大家明天見