C++ 双指针算法:求解盛水最多的容器问题
这段代码使用双指针法来解决盛水最多的容器问题。首先定义两个指针 i 和 j 分别指向容器的左右两侧。然后通过计算当前容器的容量,即底部宽度乘以高度的较小值,并将其与之前的最大容量 res 进行比较,取较大值更新 res。
接下来,我们通过比较 height[i] 和 height[j] 的值来确定哪个指针需要移动。每次移动指针时,我们将底部宽度减 1,并且移动较小的高度对应的指针,这样可以保证不会漏掉可能的更大容量。最后,当指针 i 和 j 相遇时,遍历结束,返回最大容量 res。
总结起来,这段代码的思路是通过双指针法不断更新最大容量,遍历结束时得到最大容量。该算法的时间复杂度为 O(n),其中 n 为 height 数组的长度。
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1, res = 0;
while (i < j) {
res = height[i] < height[j] ?
max(res, (j - i) * height[i++]) :
max(res, (j - i) * height[j--]);
}
return res;
}
};
希望这段代码和解释能够帮助你理解双指针法解决盛水最多的容器问题。
原文地址: http://www.cveoy.top/t/topic/pkwJ 著作权归作者所有。请勿转载和采集!