文章

LeetCode42 对撞指针的运用

引例 - 装水容器

还是从一道相对简单的问题入手:LeetCode11 - Container With Most Water

问题概要:

给一个数组,代表一系列墙壁的高度。要求选出两个墙壁,使它们能够储存最多的水。并且:

  • 忽略墙壁的厚度
  • 忽略选定的墙壁之间的墙壁

暴力解法

可以轻松想出一个暴力解法:遍历所有墙壁的组合,找出容积最大的一个。

class Solution {
  fun maxArea(height: IntArray): Int {
    var maxArea = 0
    for (a in height.indices) {
      for (b in a + 1 until height.size) {
        maxArea = max(maxArea, min(height[a], height[b]) * (b - a))
      }
    }
    return maxArea
  }
}

这个解法时间复杂度是 O(n²),空间复杂度是 O(1)

优化

有些题目,比如 LeetCode1 - Two Sum,可以通过缓存一些数据,去除一层循环,优化到 O(n) 级别。但分析一下这一题,循环中不会用到任何之前的数据,即:每一次循环都需要实时数据进行实时计算。因此这个思路不可行 ❌

此时,一个典型的算法出现了——双指针,在这个例子里可以更具体地说是对撞指针。

对撞指针指使用两个指针(下标)初始情况下分别指向数组两端,根据一定规则每次向中间移动一个指针。当两者相遇时算法结束。

针对这一题,不难看出容积 v = min(a,b) * (p2-p1),其中 a,b 分别是 p1,p2 对应的值。初始状态下,后一个因子已经达到最大。因此若希望指针移动的过程中可以得到更大的结果,则第一个因子必须变大。而第一个因子(min(a,b))又只受 a,b 较小一方的影响。 假设这样一个情况:

4, 8, 1, 2, 9
p1          p2

此时有两种选择:

  1. p1 后移。那么有两种可能的结果:
    1. 新的数 >4,可能得到更大的容积 ✅
    2. 新的数 <=4,只会得到更小的容积 ❌
  2. p2 前移。也是两种情况:
    1. 新的数 >4,但只会得到更小的容积 ❌ 因为第一个因数还是取 p1=4 不变,宽度却变小了。
    2. 新的数 <=4,显然,容积更小了 ❌

由此可见,若希望容积变大,唯一的可能性就是移动较小的指针。这就是本题对撞指针中所谓的「按一定规则移动指针」。

a=b 的边界情况无需特殊处理,随便选一个移动就好。此时容积一定会减小,但不能由此认为算法应该终止,因为后面依然有变大的可能。

优化后代码

class Solution {
  fun maxArea(height: IntArray): Int {
    // 只有移动小的一边,结果才有可能变大。
    var maxArea = 0
    var a = 0
    var b = height.size - 1
    while (a < b) {
      maxArea = max(min(height[a], height[b]) * (b - a), maxArea)
      if (height[a] < height[b])
        a++
      else
        b--
    }
    return maxArea
  }
}

此时时间复杂度降到了 O(n) 🍻

正餐 - 收集雨水

LeetCode42 - Trapping Rain Water

问题概要:

给一个数组,代表一系列墙壁的高度。求总共可储存多少雨水。并且:

  • 墙壁厚度不可忽略
  • 墙壁会占用容积

暴力解法

如图,可储水的区域有可能是不规则的,因此不能如法炮制上一题使用 宽x高 直接计算。一个自然的想法就是:分别计算每一列的容积后求和,因为对于每一列,容积要么是 0,要么是规则矩形的面积,很好计算。

略加观察思考,可以得出每一列容积的计算公式:v = min(maxL,maxR) - height。即分别找出它两边最高的墙,取较矮的一个(这和上一题思路一致),减去当前的墙高(因为墙壁会占用容积)。

那么就可以写出对应的代码:

class Solution {
  fun trap(height: IntArray): Int {
    // 单独计算每列的容积 v = min(maxL,maxR)-h
    var total = 0
    for (i in height.indices) {
      val v = maxBoundary(height, i) - height[i]
      if (v > 0)
        total += v
    }
    return total
  }

  private fun maxBoundary(height: IntArray, pos: Int): Int {
    var maxL = 0
    for (i in 0 until pos) {
      maxL = max(maxL, height[i])
    }
    var maxR = 0
    for (i in pos + 1 until height.size) {
      maxR = max(maxR, height[i])
    }
    return min(maxL, maxR)
  }
}

时间复杂度是 O(n²)

优化

观察本题与上一题的公式,它们都有一个 min 函数。借用上一题的思路,可以得出结论:不一定要遍历找出某列两边最高的墙壁。双指针从两头向中间遍历,我们可以自然地记录「当前」的 maxL 与 maxR,如果把其中一个指针作为要计算容积的列,那么它的 maxL 或 maxR 一定有一个是可以准确确定的。至于另一个,我们并不关心,因为如果我们规定只对较矮的一个指针进行操作,那么那个不确定的值本来就不会影响结果(min 函数只取较小的一个)。

比如起始情况:

0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1
p1                               p2

此时 p1 比较矮,那么我们对 p1 进行操作。它的 maxL=0,maxR 无所谓,v = min(0,maxR) - 0 = 0。然后令 p1 右移。

不妨规定 p1 p2 高度相等时依然对 p1 操作。(规定对 p2 操作不影响最终结果),那么循环到如下情况:

0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1
      p1                         p2

此时 p1=0,p2=1,显然应该对 p1 操作。此时 maxL=1 是确定的,maxR 不确定但肯定 >=1。根据公式可以算出 v= min(1,1)-0 = 1

以此类推就可以算出所有列的容积。

整理一下核心步骤:

  1. 对较矮的一边进行操作。
  2. 若高度低于同侧的最大高度则计算容积;
  3. 否则更新最大高度。
  4. 向中间移动指针,

优化后代码

class Solution {
  fun trap(height: IntArray): Int {
    var a = 0
    var b = height.size - 1
    var maxL = 0
    var maxR = 0
    var total = 0
    while (a < b) {
      if (height[a] < height[b]) {
        if (height[a] > maxL) {
          maxL = height[a]
        } else {
          total += maxL - height[a]
        }
        a++
      } else {
        if (height[b] > maxR) {
          maxR = height[b]
        } else {
          total += maxR - height[b]
        }
        b--
      }
    }
    return total
  }
}

时间复杂度为 O(n)