Code Wars Twice Linear问题：动态规划解法超时求助

嘿，我碰到过类似的问题，这个数列的生成逻辑和经典的丑数问题高度相似，你用动态规划出现超时，大概率是因为没有避免重复计算或者遍历方式不够高效。下面给你两个靠谱的优化方案：

方案一：双指针法（最优，O(n)时间复杂度） #

这个思路的核心是：数列中的每个数都是由前面的数通过2x+1或3x+1生成的，我们可以用两个指针分别跟踪这两种生成方式的候选位置，每次选择较小的候选值加入数列，同时移动对应的指针（如果两个候选值相等，两个指针都移动，避免重复）。

示例代码（JavaScript） #

function generateSequence(n) {
  const sequence = [1];
  let pointer2 = 0, pointer3 = 0;

  for (let i = 1; i < n; i++) {
    const nextFrom2 = 2 * sequence[pointer2] + 1;
    const nextFrom3 = 3 * sequence[pointer3] + 1;
    const nextValue = Math.min(nextFrom2, nextFrom3);

    sequence.push(nextValue);
    // 移动对应指针，若两个值相等则同时移动，避免重复添加
    if (nextValue === nextFrom2) pointer2++;
    if (nextValue === nextFrom3) pointer3++;
  }

  return sequence;
}

为什么高效？ #

每个指针只会单向向前移动，不会回头，整个过程是线性遍历，没有重复计算，也不需要额外的空间存储候选值（除了结果数组），完全不会出现超时问题。

方案二：最小堆（优先队列），O(n logn)时间复杂度 #

如果双指针的逻辑一时不好理解，用最小堆也是个不错的选择。我们用堆来维护所有候选的下一个数，每次弹出堆顶的最小值（保证数列有序），然后生成对应的2x+1和3x+1，用集合去重后加入堆中。

示例代码（JavaScript） #

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return min;
  }

  bubbleUp(idx) {
    const val = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (val >= parent) break;
      this.heap[idx] = parent;
      this.heap[parentIdx] = val;
      idx = parentIdx;
    }
  }

  sinkDown(idx) {
    const length = this.heap.length;
    const val = this.heap[idx];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let swapIdx = null;

      if (leftChildIdx < length && this.heap[leftChildIdx] < val) {
        swapIdx = leftChildIdx;
      }
      if (rightChildIdx < length) {
        const rightChild = this.heap[rightChildIdx];
        if ((swapIdx === null && rightChild < val) || (swapIdx !== null && rightChild < this.heap[swapIdx])) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      this.heap[idx] = this.heap[swapIdx];
      this.heap[swapIdx] = val;
      idx = swapIdx;
    }
  }
}

function generateSequence(n) {
  const heap = new MinHeap();
  const seen = new Set();
  const sequence = [];

  heap.push(1);
  seen.add(1);

  for (let i = 0; i < n; i++) {
    const current = heap.pop();
    sequence.push(current);

    const next2 = 2 * current + 1;
    if (!seen.has(next2)) {
      seen.add(next2);
      heap.push(next2);
    }

    const next3 = 3 * current + 1;
    if (!seen.has(next3)) {
      seen.add(next3);
      heap.push(next3);
    }
  }

  return sequence;
}

为什么能解决超时？ #

堆的弹出和插入操作是O(logk)（k为堆的大小），加上去重的集合操作，整体时间复杂度是O(n logn)，对于大部分场景来说效率足够，不会出现超时。

内容的提问来源于stack exchange，提问作者user9515918