2048. Next Greater Numerically Balanced Number

Next Greater Numerically Balanced Number

題目描述： 一個數字是「數值平衡」的，如果每個出現的數字 d 恰好出現 d 次。例如 1210 不是（0 出現了 1 次但不是 0 次），而 1224444 是（1 出現 1 次、2 出現 2 次、4 出現 4 次）。給定整數 n，找到大於 n 的最小數值平衡數。

解題思路： 由於 n 最大為 10^6，答案最多為 7 位數。數值平衡數的數量非常有限，最直接的方法是逐一檢查 n+1, n+2, ... 直到找到一個數值平衡數。

判斷一個數是否為數值平衡數：統計每個數字出現的次數，檢查每個出現過的數字 d 是否恰好出現 d 次，且未出現的數字出現次數為 0。

n 最大為 10^6，而下一個數值平衡數不會離 n 太遠（最多幾千步），因此暴力枚舉足夠高效。

時間複雜度：O(G * D) — G 為從 n+1 到下一個平衡數的距離（實測最多不超過幾千），D 為數字的位數（最多 7 位）。整體而言非常快速。

空間複雜度：O(1) — 僅使用固定大小的計數陣列。

1. 預計算所有平衡數：由於 7 位數以內的數值平衡數非常少（約一百多個），可以用回溯法枚舉所有可能的組合（如 1 個 1、2 個 2、3 個 3 等），生成所有排列，排序後用二分搜尋找到大於 n 的最小值。預處理 O(C) 後查詢 O(log C)，C 為平衡數總數。

2. 組合數學構造法：先確定位數 k，然後將 k 分配給各個數字（如 k=4 可以分為 1+3 或 4 或 2+2 或 1+1+2），再用排列組合生成所有可能的數字。這避免了逐一枚舉，但實作較複雜。

1. 如果 n 可以到 10^18，暴力枚舉不再可行，如何用組合構造法直接找到答案？
2. 能否在 O(1) 或 O(log n) 時間內判斷一個範圍 [a, b] 中有多少個數值平衡數？
3. 若將「數字 d 出現 d 次」改為「數字 d 出現 d+1 次」，平衡數的分布會如何變化？