Initial Solution
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
curLeft = 0
curRight = n-1
area = -1
while curLeft < curRight:
area = max(self.calArea(curLeft, curRight, height), area)
if height[curLeft] > height[curRight]:
curRight -=1
else :
curLeft += 1
return area
def calArea(self, a, b, height):
y1 = height[a]
y2 = height[b]
width = b - a
height = min(y1,y2)
return height * width
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n) where n is the length of the height array. We traverse the array once using two pointers from both ends.
Space Complexity: O(1) as we only use a constant amount of extra space for variables (curLeft, curRight, area).
Other Better Solutions
The initial solution already uses an optimal two-pointer approach, which is the most efficient algorithm for this problem. The key insight is moving the pointer with the smaller height, as moving the larger height pointer can only decrease the area.
An alternative implementation might use slightly different variable names or logic structure, but the time and space complexity would remain the same since O(n) time and O(1) space are already optimal for this problem.