Two pointers. Time = O(n), space = O(1). 可以参考这个帖子看粗略证明.
Java:
class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int maxArea = 0;
while (i < j) {
int curMax = (j - i) * Math.min(height[i], height[j]);
maxArea = Math.max(maxArea, curMax);
if (height[i] <= height[j]) {
i ++;
} else {
j --;
}
}
return maxArea;
}
}
Python:
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
left = 0
right = len(height) - 1
max_area = 0
while left < right:
max_area = max(max_area, (right - left) * min(height[left], height[right]))
if height[left] < height[right]:
left += 1
elif height[left] > height[right]:
right -= 1
else:
left += 1
right -= 1
return max_area