目标
如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。
给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。
示例 1：
输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次
这也是严格大于 1 的最小数值平衡数。示例 2：
输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。示例 3：
输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。
这也是严格大于 3000 的最小数值平衡数。说明：
- 0 <= n <= 10^6
思路
定义平衡数中每一位上数字的出现次数 cnt[d] = d，判断大于 n 的最小平衡数。
回溯构造 10^7 范围内的所有平衡数，然后二分查找。
官网题解是枚举所有大于 n 的整数，判断是否是平衡数，也可以预处理 (n, 1224444] 范围内的所有平衡数，然后二分查找。
代码
/**
* @date 2025-10-24 9:12
*/
public class NextBeautifulNumber2048 {
public int nextBeautifulNumber(int n) {
return set.higher(n);
}
private static final TreeSet<Integer> set = new TreeSet<>();
static {
int[] cnt = new int[7];
Arrays.setAll(cnt, i -> i);
dfs(0, 0, 7, cnt);
}
public static void dfs(int cur, int l, int length, int[] cnt) {
if (l > length + 1) {
return;
}
boolean balance = true;
for (int i = 1; i < cnt.length; i++) {
if (cnt[i] != i && cnt[i] != 0) {
balance = false;
break;
}
}
if (balance) {
set.add(cur);
}
for (int i = 1; i < cnt.length; i++) {
if (cnt[i] == 0) {
continue;
}
cnt[i]--;
dfs(cur * 10 + i, l + 1, length, cnt);
cnt[i]++;
}
}
}
性能
