【朱迪的LeetCode刷题笔记】】11. Container With Most Water #Medium #Python
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height).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.
Example 1:
Input: height =
Output: 49
Explanation: The above vertical lines are represented by array . In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height =
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height <= 104
Hint
(1/3)
If you simulate the problem, it will be O(n^2) which is not efficient.
Hint
(2/3)
Try to use two-pointers. Set one pointer to the left and one to the right of the array. Always move the pointer that points to the lower line.
Hint
(3/3)
How can you calculate the amount of water at each step?
Judy
Python inspired by hints
class Solution(object):
def maxArea(self, height):
"""
:type height: List
:rtype: int
"""
l = len(height)
i = 0
j = l-1
c = 0
while i != j:
if height < height:
if (j-i) * height > c:
c = (j-i) * height
i += 1
else:
if (j-i) * height > c:
c = (j-i) * height
j -= 1
return c
强{:10_275:}
页:
[1]