解决方案

方法一：存储索引

思路

由于我们想要检查数字 N 的二进制表示法中连续的 1 之间的距离，让我们先记录下该二进制表示中每个 1 的索引。例如，如果 N = 22 = 0b10110，那么我们将记录 A = [1, 2, 4]。这使得我们可以容易地继续，原问题被转换为关于数组中相邻值的问题。

算法

创建一个关于索引 i 的列表 A， N 在第 i 位上的值为 1。

有了这个数组 A，找到连续的 1 之间的距离就变得容易得多：它会是这个数组相邻值之间的最大差值。

复杂度分析

• 时间复杂度： $$O(\log N)$$ ，注意 $$\log N$$ 是 $$N$$ 的二进制表示的位数。

• 空间复杂度： $$O(\log N)$$ ，为数组 A 用掉的空间。
  
  

方法二：一次遍历

思路

在方法一中，我们创建了一个关于索引 i 的数组 A，其中 N 在第 i 位上的值为 1。

因为我们只关心数组 A 中连续的值，所以我们不需要存储整个数组。我们只需要记住看到的最后一个值。

算法

我们将存储 last，这是被添加到虚拟数组 A 中的最后一个值。如果 N 的第 i 位（此处应当有索引 last < i ）为 1，那么一个候选答案就是 i - last，然后新增到 A 的最后一个值被更新为 i，即 last = i。

复杂度分析

• 时间复杂度： $$O(\log N)$$ ，注意 $$\log N$$ 是 $$N$$ 的二进制表示的位数。

• 空间复杂度： $$O(1)$$ 。