比如我们计算 n 面积的时候,假如左侧的线段高度比右侧的高度低,那么我们通过左移右指针来将长度缩短为 n - 1 的做法是没有意义的,因为新形成的面积变成了(n-1) * heightOfLeft, 这个面积一定比刚才的长度为 n 的面积 (n * heightOfLeft) 小。
也就是说最大面积一定是当前的面积或者通过移动短的端点得到。
关键点解析
双指针优化时间复杂度
代码
语言支持:JS,C++,Python
JavaScript Code:
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
if (!height || height.length <= 1) return 0;
let leftPos = 0;
let rightPos = height.length - 1;
let max = 0;
while (leftPos < rightPos) {
const currentArea =
Math.abs(leftPos - rightPos) *
Math.min(height[leftPos], height[rightPos]);
if (currentArea > max) {
max = currentArea;
}
// 更新小的
if (height[leftPos] < height[rightPos]) {
leftPos++;
} else {
// 如果相等就随便了
rightPos--;
}
}
return max;
};
C++ Code:
class Solution {
public:
int maxArea(vector<int>& height) {
auto ret = 0ul, leftPos = 0ul, rightPos = height.size() - 1;
while( leftPos < rightPos)
{
ret = std::max(ret, std::min(height[leftPos], height[rightPos]) * (rightPos - leftPos));
if (height[leftPos] < height[rightPos]) ++leftPos;
else --rightPos;
}
return ret;
}
};
Python Code:
class Solution:
def maxArea(self, heights):
l, r = 0, len(heights) - 1
ans = 0
while l < r:
ans = max(ans, (r - l) * min(heights[l], heights[r]))
if heights[r] > heights[l]:
l += 1
else:
r -= 1
return ans
复杂度分析
时间复杂度:由于左右指针移动的次数加起来正好是 n, 因此时间复杂度为 $O(N)$。
空间复杂度:$O(1)$。
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。