- Container With Most Water
- Misunderstood question
- My First Method
- Fisrt Python code
- My Second Method
- Second Python code
Container With Most Water
The origianl question is as follow.
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.
Misunderstood question
At first I misunderstood the meaning of the question. I wonder there are many line, and if we pull as much as water into the lines, what will happen.
In order to solve this misunderstood question, I use some method. Such as set a Dynamic Programme Matrix, from the two side reach to the highest line. And change the True or False situation.
Then I use some recursive function. The code is as follows.
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
highest = 0
flag = 0
for i in range(len(height)):
if height[i] > highest:
highest = height[i]
flag = i
print flag
print highest
if flag == 0:
pass
else:
for i in range(flag-1):
if height[i+1] < height[i]:
height[i+1] = height[i]
if flag == len(height):
pass
else:
for i in range(len(height)-1,flag+1,-1):
print i
if height[i] > height[i-1]:
height[i-1] = height[i]
area = 0
for i in range(flag):
area = area + height[i]
print flag
print len(height)
for i in range(len(height)-1,flag,-1):
area = area + height[i]
return area
My First Method
Calculate all the situation. Time consuming is N square and Space consuming is 1.
Fisrt Python code
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
area = 0
for i in range(len(height)-1):
for j in range(i+1,len(height)):
area = max(area, min(height[i],height[j])*(j-i))
return area
My Second Method
Use two nodes, initially is the maximum range. Which node the value is smaller, change to inside one. Until reach together.
Second Python code
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
start = 0
end = len(height) - 1
area = 0
while start != end:
area = max(area,(end-start)*min(height[end],height[start]))
if height[start] < height[end]: start += 1
else: end -= 1
return area
近期评论