1 """ 2 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. 3 Note: You may not slant the container and n is at least 2. 4 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. 5 Example: 6 Input: [1,8,6,2,5,4,8,3,7] 7 Output: 49 8 """ 9 """ 10 解法一：暴力解法 11 对数据量大，超时 12 Time Limit Exceeded 13 """ 14 class Solution1: 15 def maxArea(self, height): 16 most_water = 0 17 if len(height) < 2: 18 return 0 19 for i in range(len(height)-1): 20 for j in range(i+1, len(height)): 21 h = min(height[i], height[j]) 22 most_water = max(most_water, h*(j - i)) 23 return most_water 24 25 """ 26 解法二：双指针法 27 让i=0, j=len(height)-1,从而保证底最长 28 如果高nums[i] < nums[j] i++ 29 否则j-- 30 当重合i == j 退出迭代 31 """ 32 class Solution2: 33 def maxArea(self, height) -> int: 34 most_water = 0 35 if len(height) < 2: 36 return 0 37 i = 0 38 j = len(height) - 1 39 while i < j: 40 h = min(height[i], height[j]) 41 most_water = max(most_water, h*(j-i)) 42 if height[i] < height[j]: 43 i += 1 44 else: 45 j -= 1 46 return most_water