Day 9 - Container With Most Water

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
废话不多说开始今天的解题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;
}