题目链接:11. 盛最多水的容器
方法:相向双指针
解题思路
- 根据题目要求,\(2 <= n <= 10^5\),可知如果使用暴力求解,显然会超时。
- 使用双指针算法可以大大缩短时间复杂度,取 \([i, j]\) 双指针,初始化为 $i = 0, j = n - 1, i < j, $ 最大面积 \(s = 0;\)
- 假设某时 \(height[i] <= height[j]\),则比 \([i, j]\) 区间能够找出更大面积的区间应该为 \([i + 1, j]\),反之为 \([i, j - 1]\)。因为以 \(height[i]\) 为边所能组成的最大面积就是 \(height[i] * (j - i)\),要想面积更大只能在 \([i + 1, j]\) 中选取。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
int s = 0;
for (int i = 0, j = height.size() - 1; i < j; ) {
s = max(s, min(height[i], height[j]) * (j - i));
if (height[i] <= height[j]) i ++ ;
else j -- ;
}
return s;
}
};
复杂度分析
时间复杂度:\(O(n)\);
空间复杂度:\(O(1)\)。