方法一:双指针
-
考察:
贪心、数组、双指针 -
说明
本题是一道经典的面试题,最优的做法是使用「双指针」。如果读者第一次看到这题,不一定能想出双指针的做法。
复杂度分析
时间复杂度:O(N),双指针总计最多遍历整个数组一次。文章来源:https://www.uudwc.com/A/aYDwn/
空间复杂度:O(1),只需要额外的常数级别的空间。文章来源地址https://www.uudwc.com/A/aYDwn/
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;
}
}