# -*- coding: utf-8 -*-

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

# 还是理解题意, 每一个点对应的是一个各县段[(i, ai), (i, 0)], 题目的意思是要找到两个点, 这两个点对对应的线段和x轴围成的"水桶"最大.

class Solution:
    def Container(self, nums):
        max_contain = 0
        i = 0
        j = len(nums) - 1
        # 这个题的技巧在于利用题目性质. 知道了算法, 题目并不难
        # 设定两个指针,分别指向首位, 每次只移动数字小的指针, 因为只有保证数字小的最大才能保证谁最多.
        while True:
            if i == j:
                break
            if nums[i] < nums[j]:
                i += 1
                max_contain = max(max_contain, min(nums[i], nums[j]) * (j - i))
            else:
                j -= 1
                max_contain = max(max_contain, min(nums[i], nums[j]) * (j - i))
        return max_contain

height = [1, 2, 3, 4, 3, 2, 1, 5]
result = Solution().Container(height)
print result

# Time:  O(n)
# Space: O(1)