分治的经典应用

汉诺塔如何用分治求解？

• 问题: 把 $n$ 个圆盘从 A 柱经 B 柱移到 C 柱, 每次只能移动一个且大盘不能压小盘;
• 分: 把顶部 $n - 1$ 个圆盘看作整体;
• 三步: ① $n-1$ 从 A 经 C 移到 B; ② 剩下 1 个从 A 移到 C; ③ $n-1$ 从 B 经 A 移到 C;
• 递推式: $f(n) = 2f(n-1) + f(1)$, 终止条件为只剩 1 个圆盘时直接移动;

const hanota = (A, B, C) => {
  const dfs = (n, from, buffer, to) => {
    if (n === 1) {
      to.push(from.pop());
      return;
    }
    dfs(n - 1, from, to, buffer); // n-1 从 from 经 to 移到 buffer
    to.push(from.pop()); // 最大盘直接移入 to
    dfs(n - 1, buffer, from, to); // n-1 从 buffer 经 from 移到 to
  };

  dfs(A.length, A, B, C);
};

• 关键: 三次移动中, 出发柱、缓冲柱、目标柱的角色随递归层交换;

合并 k 个有序链表如何用分治求解？

• 等价: 把归并排序中"按中点划分单链表"换成"按下标划分链表数组";
• 分: 把链表数组从中间切成两半;
• 治: 两个有序链表按双指针归并;
• 优势: 相比逐个归并的 $O(k^2 n)$, 分治两两归并只需 $O(k n \log k)$;

const mergeKLists = (lists) => {
  const merge = (l1, l2) => {
    const dummy = new ListNode(-1);
    let cur = dummy;
    while (l1 && l2) {
      if (l1.val < l2.val) {
        cur.next = l1;
        l1 = l1.next;
      } else {
        cur.next = l2;
        l2 = l2.next;
      }
      cur = cur.next;
    }
    cur.next = l1 ?? l2;
    return dummy.next;
  };

  const mergeK = (left, right) => {
    if (left >= right) return lists[left];
    const mid = left + ((right - left) >> 1);
    return merge(mergeK(left, mid), mergeK(mid + 1, right));
  };

  return lists.length === 0 ? null : mergeK(0, lists.length - 1);
};

快速幂如何用分治把复杂度降到对数级？

• 目标: 计算 $x^n$;
• 分: 由指数的奇偶性拆成同底数的更小幂;
  • $n$ 为偶数: $x^n = (x^2)^{n/2}$;
  • $n$ 为奇数: $x^n = x \cdot (x^2)^{\lfloor n/2 \rfloor}$;
• 治: 每层只算一个子问题, 所以不是标准二分而是"减半";
• 边界: $n < 0$ 时先取倒数并取反指数, $n = 0$ 时返回 1;

const myPow = (x, n) => {
  if (n < 0) return myPow(1 / x, -n);
  if (n === 0) return 1;
  const half = myPow(x * x, Math.floor(n / 2));
  return n % 2 === 0 ? half : x * half;
};

• 复杂度: 时间 $O(\log n)$, 空间 $O(\log n)$;

验证二叉搜索树的后序序列如何分治？

• 依据: 后序遍历顺序为"左 → 右 → 根", 数组最右元素是当前子树的根;
• 划分: 从左向右找到第一个大于根的元素, 其左侧是左子树、右侧是右子树;
• 校验: 右子树内必须全部大于根; 满足则递归校验两个子数组;

const verifyTreeOrder = (postorder) => {
  const dfs = (left, right) => {
    if (left >= right) return true;
    let index = left;
    while (postorder[index] < postorder[right]) index++; // 左子树边界
    const mid = index;
    while (postorder[index] > postorder[right]) index++; // 跳过右子树
    return index === right && dfs(left, mid - 1) && dfs(mid, right - 1);
  };

  return dfs(0, postorder.length - 1);
};

• 复杂度: 时间 $O(n^2)$ (退化为链时), 空间 $O(n)$;
• 边界: 空区间与单元素区间直接返回 true, 对应 left >= right;

寻找两个正序数组的中位数如何用分治求解？

• 目标: 在两个有序数组中取第 $k$ 小元素, $k = \lfloor (m + n + 1) / 2 \rfloor$;
• 分: 设 nums1 取前 $a$ 个、nums2 取前 $k - a$ 个, 在 $[0, m]$ 上二分 $a$;
• 判定: nums1[a] < nums2[k - a - 1] 说明前 $k$ 小还缺 nums1 的元素, 令 left = mid + 1; 否则 right = mid;
• 合并: 取两个候选左侧元素的最大值; 总长度为偶数时再与右侧最小值取平均;
• 前提: 先交换数组, 保证 nums1 更短, 这样 $a$ 的范围最小且不会越界;

const findMedianSortedArrays = (nums1, nums2) => {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const k = Math.floor((nums1.length + nums2.length + 1) / 2);
  let left = 0;
  let right = nums1.length;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums1[mid] < nums2[k - mid - 1]) left = mid + 1;
    else right = mid;
  }
  const m = k - left;
  const v1 = Math.max(left <= 0 ? -Infinity : nums1[left - 1], m <= 0 ? -Infinity : nums2[m - 1]);
  if ((nums1.length + nums2.length) % 2 === 1) return v1;
  const v2 = Math.min(
    left >= nums1.length ? Infinity : nums1[left],
    m >= nums2.length ? Infinity : nums2[m],
  );
  return (v1 + v2) / 2;
};

• 复杂度: 时间 $O(\log \min(m, n))$, 空间 $O(1)$;
• 边界: 某个数组取 0 个元素时, 对应候选值视为 $-\infty$ / $+\infty$;