LeetCode 902 同类题对比：3种解法剖析“最大为 N 的数字组合”问题-平芜编程栈

LeetCode 902 同类题对比：3种解法剖析“最大为 N 的数字组合”问题

1. 问题本质与算法选择逻辑

数字组合类问题在算法面试中属于高频题型，其核心在于如何高效地枚举或构造满足条件的数字。LeetCode 902（最大为 N 的数字组合）与字节面试题（找小于n的最大数）具有高度相似性，但存在两个关键差异点：

数字可重复性：字节题允许数字重复使用，而LeetCode 902通常限制每个数字只能使用一次
零的处理：字节题明确数字不含0，而LeetCode 902可能包含0需要特殊处理

针对这类问题，常见的三种解法具有不同的适用场景：

算法类型	时间复杂度	空间复杂度	适用场景
回溯法	O(k^n)	O(n)	小规模数据，需要所有解
贪心+二分	O(n logk)	O(1)	有序数字集合，快速定位
数位DP	O(logN)	O(logN)	大规模数据，统计类问题

提示：面试中优先考虑贪心+二分的组合解法，它能在合理时间内解决问题且代码相对简洁

2. 回溯法：暴力搜索的优化艺术

回溯法是解决组合问题的通用解法，通过递归探索所有可能的数字排列。以字节面试题为例，其Python实现核心逻辑如下：

class Solution: def maxNumber(self, nums, n): self.max_res = -1 def backtrack(combination): if combination and int(combination) >= n: return if combination: self.max_res = max(self.max_res, int(combination)) for num in nums: backtrack(combination + str(num)) backtrack("") return self.max_res

关键优化点：

剪枝策略：当当前组合已经大于等于n时立即返回
提前终止：记录全局最大值，避免无效搜索
数字排序：预处理将nums排序可加速找到解

实际测试案例：

nums = [2,8,8,6,7] n = 88888 print(Solution().maxNumber(nums, n)) # 输出88776

3. 贪心+二分：高效定位最优解

贪心算法结合二分查找是本类问题的最优解法，其核心思想是：

高位优先匹配：从最高位开始尽可能匹配n-1的对应数字
二分加速查找：在有序nums中快速定位小于等于目标值的最大数
降级处理：当某位无法匹配时，回退到前一位减一

完整实现代码及注释：

def find_max_number(nums, limit): nums.sort() limit -= 1 # 目标变为≤limit-1的最大数 s_limit = str(limit) def bisect(target): # 在nums中找≤target的最大数 left, right = 0, len(nums) res = -1 while left < right: mid = (left + right) // 2 if nums[mid] <= target: res = nums[mid] left = mid + 1 else: right = mid return res def dfs(index): if index == len(s_limit): return int(s_limit) curr = int(s_limit[index]) near = bisect(curr) if near == -1: # 当前位无合适数字 return -1 elif near == curr: # 当前位匹配成功 res = dfs(index + 1) if res != -1: return res if near > 0: # 尝试减小当前位 return int(s_limit[:index] + str(nums[bisect(curr-1)]) + str(nums[-1])*(len(s_limit)-index-1)) return -1 else: # 当前位已减小 return int(s_limit[:index] + str(near) + str(nums[-1])*(len(s_limit)-index-1)) res = dfs(0) if res != -1: return res # 处理位数减少的情况 return int(str(nums[-1])*(len(s_limit)-1)) if len(s_limit)>1 else -1

算法执行流程示例：

输入: nums = [2,4,9], n = 2531 步骤: 1. 处理n-1=2530 2. 千位2→匹配2 3. 百位5→匹配4 4. 后续位填最大值9→返回2499

4. 数位DP：处理大规模数据的利器

数位动态规划适合处理极大范围的数字统计问题。其核心是记忆化搜索，通过dp[pos][tight][lead]记录状态：

pos：当前处理数位位置
tight：前面位数是否严格等于n的对应位
lead：是否有前导零

LeetCode 902的标准数位DP解法：

def atMostNGivenDigitSet(digits, n): s = str(n) k = len(s) dp = [{} for _ in range(k)] def dfs(pos, tight, lead): if pos == k: return 0 if lead else 1 if (tight, lead) in dp[pos]: return dp[pos][(tight, lead)] limit = int(s[pos]) if tight else 9 res = 0 for d in map(int, digits): if d > limit: continue new_tight = tight and (d == limit) new_lead = lead and (d == 0) res += dfs(pos+1, new_tight, new_lead) dp[pos][(tight, lead)] = res return res return dfs(0, True, True)

状态转移分析：