方法一:双指针
- 考察:
贪心、数组、双指针 - 说明
本题是一道经典的面试题,最优的做法是使用「双指针」。如果读者第一次看到这题,不一定能想出双指针的做法。
复杂度分析
时间复杂度:O(N),双指针总计最多遍历整个数组一次。
空间复杂度:O(1),只需要额外的常数级别的空间。
public class Solution { public int maxArea(int[] height) { int l = 0, r = height.length - 1; int ans = 0; while (l < r) { int area = Math.min(height[l], height[r]) * (r - l); ans = Math.max(ans, area); if (height[l] <= height[r]) { ++l; } else { --r; } } return ans; } }