题目描述
思路解析动画文字版
记牢这一句:从 n 的下一个数开始,挨个试。判定一个数平不平衡,就看它每个数位 d 是不是恰好出现 d 次。下面从 14 开始,一步一步试到 22。
候选队列 · 从 n+1 = 14 开始逐个试：这一排就是我们要挨个验的候选,从 n 加 1 也就是 14 开始,一直往上。算法很朴素:排头这个先试,不平衡就划掉换下一个,直到撞上第一个平衡数。紫色高亮的就是当前正在试的候选,现在轮到 14。
试 14 · 拆数位,填计数桶 cnt：轮到候选 14。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。14 拆出来是 1 和 4,统计下来 数位 1 出现 1 次,数位 4 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 14 · 数位 4 出现 1 次,却需要出现 4 次,淘汰：判定 14。数位 1 那一位是对上了,数位 4 出现 1 次,却需要出现 4 次,这一位对不上,整个数就不平衡。把 14 划掉,枚举指针往前挪一格,去试 15。
试 15 · 拆数位,填计数桶 cnt：轮到候选 15。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。15 拆出来是 1 和 5,统计下来 数位 1 出现 1 次,数位 5 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 15 · 数位 5 出现 1 次,却需要出现 5 次,淘汰：判定 15。数位 1 那一位是对上了,数位 5 出现 1 次,却需要出现 5 次,这一位对不上,整个数就不平衡。把 15 划掉,枚举指针往前挪一格,去试 16。
试 16 · 拆数位,填计数桶 cnt：轮到候选 16。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。16 拆出来是 1 和 6,统计下来 数位 1 出现 1 次,数位 6 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 16 · 数位 6 出现 1 次,却需要出现 6 次,淘汰：判定 16。数位 1 那一位是对上了,数位 6 出现 1 次,却需要出现 6 次,这一位对不上,整个数就不平衡。把 16 划掉,枚举指针往前挪一格,去试 17。
试 17 · 拆数位,填计数桶 cnt：轮到候选 17。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。17 拆出来是 1 和 7,统计下来 数位 1 出现 1 次,数位 7 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 17 · 数位 7 出现 1 次,却需要出现 7 次,淘汰：判定 17。数位 1 那一位是对上了,数位 7 出现 1 次,却需要出现 7 次,这一位对不上,整个数就不平衡。把 17 划掉,枚举指针往前挪一格,去试 18。
试 18 · 拆数位,填计数桶 cnt：轮到候选 18。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。18 拆出来是 1 和 8,统计下来 数位 1 出现 1 次,数位 8 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 18 · 数位 8 出现 1 次,却需要出现 8 次,淘汰：判定 18。数位 1 那一位是对上了,数位 8 出现 1 次,却需要出现 8 次,这一位对不上,整个数就不平衡。把 18 划掉,枚举指针往前挪一格,去试 19。
试 19 · 拆数位,填计数桶 cnt：轮到候选 19。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。19 拆出来是 1 和 9,统计下来 数位 1 出现 1 次,数位 9 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 19 · 数位 9 出现 1 次,却需要出现 9 次,淘汰：判定 19。数位 1 那一位是对上了,数位 9 出现 1 次,却需要出现 9 次,这一位对不上,整个数就不平衡。把 19 划掉,枚举指针往前挪一格,去试 20。
进度小结 · 14 到 19 已淘汰：试到这里停一下看看进度。14 到 19 这六个已经全被划成灰色,它们淘汰的原因其实一模一样:除了数位 1 是出现 1 次刚好达标,另一个数位比如 4 到 9,都只出现了 1 次,可它们要求出现自己那么多次,次数远远不够。接着往下,轮到 20,这个数里藏着 0,会更干脆地出局。
试 20 · 拆数位,填计数桶 cnt：轮到候选 20。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。20 拆出来是 2 和 0,统计下来 数位 0 出现 1 次,数位 2 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 20 · 数位 2 出现 1 次,却需要出现 2 次,淘汰：判定 20。数位 2 出现 1 次,却需要出现 2 次,这一位对不上,整个数就不平衡。注意数位 0:它一出现就必然违规,因为平衡数要求 0 出现 0 次,自相矛盾。把 20 划掉,枚举指针往前挪一格,去试 21。
试 21 · 拆数位,填计数桶 cnt：轮到候选 21。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。21 拆出来是 2 和 1,统计下来 数位 1 出现 1 次,数位 2 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 21 · 数位 2 出现 1 次,却需要出现 2 次,淘汰：判定 21。数位 1 那一位是对上了,数位 2 出现 1 次,却需要出现 2 次,这一位对不上,整个数就不平衡。把 21 划掉,枚举指针往前挪一格,去试 22。
试 22 · 拆数位,填计数桶 cnt：轮到候选 22。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。22 拆出来是 2 和 2,统计下来 数位 2 出现 2 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
判定 22 · 每位都配平,命中!：判定 22。它只有数位 2,而 2 恰好出现 2 次,cnt[2] 等于 2,完全配平。这是我们从 14 一路试上来,第一个满足条件的数。算法在这里立刻停手,把 22 返回,它就是严格大于 13 的最小平衡数。
复核 22 · 没有任何多余数位：再复核一眼,确认没漏判。cnt 这张表里只有数位 2 亮着,值是 2,其余从 0 到 9 的格子全是 0,没有任何出现了却次数对不上的数位,也没有 0 来捣乱。条件干干净净地满足,答案就锁定在 22。
收束 · 14 到 21 全淘汰,22 命中：回看整排候选。14 到 21 这八个,要么某个数位次数不够,要么含了 0,全被划成灰色淘汰掉;只有排在最后的 22 一路配平,亮成绿色。枚举从 14 走到 22,撞上第一个平衡数就返回,答案就是 22,和一开始说的对上了。
边界想清:n 等于 0 时答案是 1、n 等于 1 时要一路试到 22、n 等于 21 时下一步就撞上 22。
面试重点:暴力枚举加数位计数、范围小暴力够用可提构造优化、严格大于 n 且含 0 必淘汰。
参考代码
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 Solution: def nextBeautifulNumber(self, n: int) -> int: for x in count(n + 1): y = x cnt = [0] * 10 while y: y, v = divmod(y, 10) cnt[v] += 1 if all(v == 0 or i == v for i, v in enumerate(cnt)): return x复杂度
- 时间：O(k · d)，k 是从 n+1 到答案要枚举的候选个数,d 是每个候选的位数。数值范围内 n 不超过一百万,答案有界(平衡数分布够密,最坏也就跳到七位数附近),d 至多 7 位是常数。所以整体近似线性于要试的候选数
- 空间：O(1)，只用一个长度固定为 10 的计数桶 cnt,和几个循环变量。不随 n 增长开更多空间,也没有递归栈。判定完一个候选就把 cnt 清空复用
易错点
面试追问把动画讲成自己的话
追问这题最直接的做法是什么?
追问暴力会不会太慢,有没有更快的思路?
追问判定时有什么坑要特别小心?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
拆分成最多数目的正偶数之和
LeetCode 2178 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题