两指针技巧是如何消除需要检查每个元素与每个元素的需求的?

huangapple go评论82阅读模式
英文:

how does the two-pointer technique eliminate the need to check every element with every element?

问题

以下是翻译好的内容:

我在解决一个编程问题,其中:

给定一个长度为n的整数数组height。有n个垂直线条,使得第i条线的两个端点分别是(i, 0)和(i, height[i])。

找到两条与x轴一起形成一个容器的线条,使得容器包含最多的水。

返回容器可以存储的最大水量。

问题链接

我的答案使用了暴力方法,但建议的答案具有时间复杂度为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;
};

我理解这个解决方案的工作原理,但我仍然不理解双指针技术是如何消除需要检查每个元素与每个元素之间的需求的。能否有人解释其背后的逻辑呢?谢谢。

英文:

I was solving a coding problem where:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

https://leetcode.com/problems/container-with-most-water/description/

My answer used brute force but the suggested answer with a time complexity of O(n) was this:

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;
};

I understand how this solution works but I still dont understand how the two-pointer technique eliminates the need to check every element with every element.
could someone please explain the logic behind it?
thank you.

答案1

得分: 2

如何使用双指针技巧消除了需要检查每个元素与每个元素的需求

当你有一对(leftPointerrightPointer)时,height[leftPointer]height[rightPointer] 中较小的值决定了相应容器的容积。

假设 height[leftPointer] 是较小的(或者至少不更大)。

那么我们知道对于任何在范围 [leftPointer+1, ..., highPointer] 内的 ileftPointeri 之间的容积不可能大于我们已经有的容积。即使有一个非常高的 height[i],也无关紧要,因为此时 height[leftPointer] 较小且决定了高度。而且因为 leftPointeri 之间的距离小于 leftPointerrightPointer 之间的距离,容积永远不会超过我们已经有的容积。

因此,我们不需要访问那些 leftPointer, i 对。这就是我们避免生成所有组合的地方。

另一方面,我们不能排除存在一个 i,其中 i, highPointer 对应的容器容积更大的可能性。这就是为什么需要执行 leftPointer++,然后对新的一对进行相同推理的正确操作。

英文:

> how the two-pointer technique eliminates the need to check every element with every element

When you have a pair (leftPointer, rightPointer), then the least of height[leftPointer] and height[rightPointer] determines the volume that the corresponding container has.

Let's assume that height[leftPointer] is the lesser one (or at least not greater).

Then we know that for any i in the range [leftPointer+1, ..., highPointer] the volume between leftPointer and i cannot be greater than what we already have. Even if there would be a very high height[i] it wouldn't matter as then height[leftPointer] is the lesser and determining height. And because the distance between leftPointer and i is less than the distance between leftPointer and rightPointer, the volume can never exceed what we already have.

So we don't need to visit those leftPointer, i pairs. That's were we avoid making all combinations.

On the other hand, we cannot exclude that there is an i where the i, highPointer pair would represent a greater volume container. That is why leftPointer++ is the correct action to take, and then the same reasoning can be applied to the new pair.

huangapple
  • 本文由 发表于 2023年1月6日 18:35:30
  • 转载请务必保留本文链接:https://go.coder-hub.com/75029814.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定