我在解决一个编码问题：
给定长度为n的整数数组高度。绘制n条垂直线，使第i条线的两个端点为（i，0）和（i，height[i]）。
找出与x轴构成一个容器的两条直线，使该容器中的水最多。
返回容器所能储存的最大水量。
https://leetcode.com/problems/container-with-most-water/description/
我的答案使用了蛮力，但建议的答案与时间复杂度为O（n）如下：
var maxArea = function (height) {
let biggestArea = Number.MIN_VALUE;
let leftPointer = 0;
let rightPointer = height.length - 1;
while (leftPointer < rightPointer) {
let leftHeight = height[leftPointer];
let rightHeight = height[rightPointer];
let heightToUse = leftHeight < rightHeight ? leftHeight : rightHeight;
let area = heightToUse * (rightPointer - leftPointer);
biggestArea = Math.max(biggestArea, area);
if (leftHeight < rightHeight) {
leftPointer++;
} else {
rightPointer--;
}
}
return biggestArea;
};我明白这个解决方案是如何工作的，但我仍然不明白双指针技术是如何消除检查每个元素的需要的。有人能解释一下它背后的逻辑吗？谢谢。
1条答案
按热度按时间wh6knrhe1#
双指针技术如何消除逐个元素检查的需要
当你有一对（
leftPointer，rightPointer）时，height[leftPointer]和height[rightPointer]中最小的一个决定了相应容器的体积。让我们假设
height[leftPointer]是较小的一个（或者至少不是较大的）。那么我们知道对于
[leftPointer+1, ..., highPointer]范围内的任何i，leftPointer和i之间的体积不可能比我们已经拥有的体积“更大”，即使height[i]非常高，也没有关系，因为height[leftPointer]是较小的和决定性的高度。而且因为leftPointer和i之间的距离小于leftPointer和rightPointer之间的距离，所以体积永远不会超过我们已经拥有的体积。所以我们不需要访问那些
leftPointer, i对，也就是说我们要避免所有的组合。另一方面，我们不能排除存在
i，其中i, highPointer对表示更大容量的容器，这就是为什么leftPointer++是要采取的正确操作，然后可以将相同的推理应用于新对。