解法一:
双层循环遍历找结果,相当于是一个暴力求解方法,两层嵌套循环的时间复杂度是O(N2),所以有一些样例测试时间超时
class Solution:
def maxArea(self, height: List[int]) -> int:
max_result=0
for i in range(len(height)):
for j in range(i+1,len(height)):
temp_result=min(height[i],height[j])*abs(i-j)
if temp_result > max_result:
max_result=temp_result
return max_result
解法二:
在解法一的基础上,将双层嵌套循环改为指针,既可以实现将时间复杂度O(N2)降低为O(N)
将一个指针指向队头,一个指针指向队尾,然后更新的时候判断是哪个指针指向的值小,则小的那个指针移动。
class Solution:
def maxArea(self, height: List[int]) -> int:
max_result = 0
left = 0
right = len(height) - 1
while left < right:
temp_result = min(height[left], height[right]) * (right - left)
if temp_result > max_result:
max_result = temp_result
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_result