011. Container With Most Water

Question 11

https://leetcode.com/problems/container-with-most-water/

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

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.

Example 1:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Answer

取左右兩邊較低的一邊為高，右座標剪左座標為寬。

v1. O(n^2) - 計算所有的可能組合 固定其一邊（左邊）後，右方的邊依序往左邊

v2. O(n) - 優化 1. 設定最左邊和最右邊為起始點 2. 當左邊高於右邊時，右邊向左方前進一格。相對的如果是右邊較高或相等時，則左邊向右方一格

v1

class Solution:
    def maxArea(self, height):
        temp_max = 0
        length = len(height)
        current_left_height = 0
        current_right_height = 0
        
        for pos_left in range(0,length-1):
            if (current_left_height < height[pos_left]):
                current_left_height = height[pos_left]
                for pos_right in range(length-1, pos_left, -1):
                    if(current_right_height < height[pos_right]):
                        current_right_height = height[pos_right]
                        container = (pos_right - pos_left) * min(height[pos_right], height[pos_left])
                        temp_max = max(container,temp_max)
                current_right_height = 0
        return temp_max

v2

class Solution:
    def maxArea(self, height):
        max_container = 0
        pos_left, pos_right = 0, len(height) - 1
        
        while( pos_left < pos_right ):
            if( height[pos_left] > height[pos_right] ):
                max_container = max( max_container, ( pos_right - pos_left )*height[pos_right] )
                pos_right -= 1
            else:
                max_container = max( max_container, ( pos_right - pos_left )*height[pos_left] )
                pos_left += 1
        return max_container