aboutsummaryrefslogtreecommitdiff
path: root/container_most_water.py
blob: a028e5f4237af6545a6c8a7d7d1c3848571d4a28 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 11. Container With Most Water

"""
you are given an integer array 'height' of length 'n'. there are 'n' vertical
lines drawn such that two endpoints of the i'th line are '(i, 0)' and '(i,
height[i])'. find two lines that together with the x-axis form a container
such that the container contains the most water. return the maximum amount of
water a container can store. notice that you may not slant the container.
"""


class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right, ans = 0, len(height) - 1, 0
        while left < right:
            curr = min(height[left], height[right]) * (right - left)
            ans = max(ans, curr)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxArea(height=[1, 8, 6, 2, 5, 4, 8, 3, 7]))
    print(obj.maxArea(height=[1, 1]))