题目描述
思路解析动画文字版
记牢这套:逐位从左往右填,每个空位先试最大的数,把 v 放在 p 就要求伙伴位 p+v 在界内且空着;放下去递归,走死就撤回换小一号。数字 1 只放一个。
先看画面怎么摆。上面这一排 7 个格子就是要填的序列,下标 0 到 6,现在全是空的,用点号占位。右边「数字放置进度」列着 4、3、2、1,现在都还没放。我们从下标 0 开始,一格一格往右填,每个空位都先抢着放最大的数,好让整串字典序尽量大。
先把最关键的距离约束讲透。对数字 v,它的两次出现下标要正好相差 v。比如待会儿把 4 放在下标 0,那它的另一处就被死死钉在下标 0 加 4 也就是 4 的位置;把 2 放在下标 1,另一处就钉在 1 加 2 等于 3。所以每放一个数,其实是一次定下两格。因为要字典序最大,靠前的位置数字越大越好,我们就让每个空位都先试最大的。
从下标 0 起手,试还没放过的最大的数 4。把 4 放这里,它的伙伴位就是 0 加 4 等于 4。下标 4 落在序列长度 7 以内,不越界;而且现在是空的。两条都满足,4 可以放。
把 4 的两处都放下,下标 0 和下标 4 都填 4,这两格标绿。你看它俩的距离,4 减 0 正好是 4,符合约束。字典序最大的诀窍就在这:先把能放的最大数顶到最前面。接着去填下标 1。
来到下标 1,还是先想最大的。4 已经两处都放完了,进度面板里 4 是「已放」,跳过它,退一档去试第二大的 3。
试着把 3 放在下标 1,那它的伙伴位是 1 加 3 等于 4。可是下标 4 已经被前面的 4 占住了,这一格标红提醒。3 的第二处没地方落,放不进去,只能再退一档,去试更小的 2。这一步的退档,正是回溯里「此路不通就换一个」的味道。
改试 2。把 2 放在下标 1,伙伴位是 1 加 2 等于 3。下标 3 在界内,而且现在空着,两条都过关,2 可以放。
把 2 的两处放下,下标 1 和下标 3 都填 2,标绿。距离一验,3 减 1 等于 2,正好等于 2 本身,合法。现在序列长成 4、2、空、2、4、空、空。指针继续右移到下标 2。
到下标 2。先看最大的 4,已经放满,跳过;再看 3,3 还没放过,试试它。
把 3 放在下标 2,伙伴位是 2 加 3 等于 5。下标 5 在界内,而且现在空着,两条都满足,3 可以放。
把 3 的两处放下,下标 2 和下标 5 都填 3,标绿。距离验一下,5 减 2 等于 3,正好符合。现在序列是 4、2、3、2、4、3、空,只剩最后一格下标 6 空着了。
指针走到下标 3,发现这里早就是 2 了。它是刚才放 2 时定下的第二处,不用再管,指针直接右移。
下标 4 也已经是 4,那是最开始放 4 时钉下的第二处,同样跳过,继续右移。
下标 5 已经是 3,是刚放 3 时定下的第二处,跳过。指针走到最后一格下标 6。
到最后一格下标 6。看进度面板,4、3、2 都已经两处放满了。只剩数字 1 还没登场,而 1 全场只放一个,正好安排在这最后的空位。
把 1 放在下标 6。1 只出现一次,没有伙伴位要照顾,直接落下,标绿。所有 7 个格子都填满了,一条完整合法的序列成型:4、2、3、2、4、3、1。
成型了,回头逐个数验一遍距离。先看 4,它落在下标 0 和下标 4,两处相距 4 减 0 等于 4,正好等于 4 本身,合法。
再看 2,它落在下标 1 和下标 3,相距 3 减 1 等于 2,等于 2 本身,合法。
接着看 3,它落在下标 2 和下标 5,相距 5 减 2 等于 3,等于 3 本身,合法。
最后看 1,它只在下标 6 出现这一次,题目就要求 1 只放一个,符合。四个数字全部验过,这确实是一条合法序列。
收个尾。它之所以是字典序最大,是因为每个空位都从大到小试,只有后续能把整串填满,这个数才保留下来;本例从头到尾一路成功,所以排出 [4, 2, 3, 2, 4, 3, 1],跟开头说的对上了。正因为是从大到小搜索,第一条凑齐的完整合法序列就是字典序最大解。多说一句:n 等于 4 这一趟从大到小恰好一路顺,没真正撤销过整段;但换成 n 等于 5,中途就会走死一次,得把放下的数撤回来退一档,那时回溯的「退」才真正派上用场。
边界:n=1 只有 [1];n=2 是 [2,1,2](两个 2 相距 2);n=3 是 [3,1,2,3,2],都能手验距离约束。
三个追问:构造公式不通用且难保字典序最大,回溯最稳;撤销必须写、n=5 就会触发;复杂度最坏指数级但两条约束剪枝后 n≤20 很快。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def constructDistancedSequence(self, n: int) -> List[int]: def dfs(u): if u == n * 2: return True if path[u]: return dfs(u + 1) for i in range(n, 1, -1): if cnt[i] and u + i < n * 2 and path[u + i] == 0: cnt[i] = 0 path[u] = path[u + i] = i if dfs(u + 1): return True path[u] = path[u + i] = 0 cnt[i] = 2 if cnt[1]: cnt[1], path[u] = 0, 1 if dfs(u + 1): return True path[u], cnt[1] = 0, 1 return False path = [0] * (n * 2) cnt = [2] * (n * 2) cnt[1] = 1 dfs(1) return path[1:]复杂度
- 时间：最坏指数级，这是一棵回溯搜索树:每个空位都可能从大到小试多个数、每个数放下去又往深里递归,最坏情况下要探很多条分支,难以给出漂亮的多项式上界,通常按指数级看待。好在两条约束砍掉大量分支:一是每个数的伙伴位被距离死死钉住,能放的位置很少;二是从大到小试、第一个能成的就锁定。所以 n 不超过 20 时,实际探到的分支很少,很快出解
- 空间：O(n)，按峰值算。path 数组和 cnt 数组都是 2n 长度,是 O(n);递归最深也就填到序列末尾,深度不超过 2n 层,递归栈也是 O(n)。两者都是 O(n),合起来 O(n),和序列长度同量级
易错点
面试追问把动画讲成自己的话
追问这题能不能不用回溯,直接套个构造公式排出来?
追问演示里 n 等于 4 从头到尾没真正撤销过,那撤销这步还必须写吗?
追问复杂度到底怎么估,面试要报个数吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出不同的二进制字符串
LeetCode 1980 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题