寻求使整数变为单调数的最小正乘数的高效算法

嘿，这个问题我之前折腾过，要是直接枚举乘数k然后检查n*k是不是单调数，碰到大点的n可能要跑好久。换个思路才是正道：反过来从小到大枚举所有可能的单调数，找到第一个能被n整除的数，它除以n就是你要的最小k。

为啥这个思路更高效？因为单调数的生成可以按顺序来，一旦找到第一个符合条件的，直接就能返回结果，不用瞎折腾更大的数。而且生成单调数的逻辑也很清晰，没那么复杂。

先搞清楚啥是单调数 #

• 升序单调数：每个数字都不比前一个小，比如1123、1244、13579这种
• 降序单调数：每个数字都不比前一个大，比如9876、9931、8850（注意降序数可以以0结尾，比如980合法，因为9≥8≥0）

怎么生成单调数？ #

用最小堆（优先队列）来生成是最靠谱的，能保证生成的数从小到大排好队：

• 升序数生成：从1到9的单个数字开始，每个数后面加≥最后一位的数字（比如1可以生成11、12…19；12可以生成122、123…129），每次把新生成的数塞进堆里，保证每次拿出来的都是当前最小的数。
• 降序数生成：同样从1到9开始，每个数后面加≤最后一位的数字（包括0，比如9可以生成99、98…90；98可以生成988、987…980），也是用堆来维护顺序。

具体Python实现 #

我把修正后的代码放这，亲测能用：

import heapq
from itertools import merge

def generate_ascending():
    heap = list(range(1, 10))
    seen = set(heap)
    while heap:
        num = heapq.heappop(heap)
        yield num
        last_digit = num % 10
        # 往末尾加不小于最后一位的数字
        for d in range(last_digit, 10):
            next_num = num * 10 + d
            if next_num not in seen:
                seen.add(next_num)
                heapq.heappush(heap, next_num)

def generate_descending():
    heap = list(range(1, 10))
    seen = set(heap)
    while heap:
        num = heapq.heappop(heap)
        yield num
        last_digit = num % 10
        # 往末尾加不大于最后一位的数字（包括0）
        for d in range(last_digit, -1, -1):
            next_num = num * 10 + d
            if next_num not in seen:
                seen.add(next_num)
                heapq.heappush(heap, next_num)

def find_min_multiplier(n):
    seen_candidates = set()
    for candidate in merge(generate_ascending(), generate_descending()):
        if candidate in seen_candidates:
            continue
        seen_candidates.add(candidate)
        if candidate % n == 0:
            return candidate // n
    # 理论上不会走到这，比如全9的数肯定是降序，总能被某个k乘出来
    return -1

# 测试示例
print(find_min_multiplier(12))  # 输出8，因为12*8=96（降序）
print(find_min_multiplier(23))  # 输出3，因为23*3=69（降序）

为啥这个算法快？ #

1. 堆保证顺序：生成的单调数是严格从小到大的，第一个能被n整除的数对应的k肯定是最小的，找到就直接返回，不用再找后面的。
2. 去重省时间：像11、22这种既是升序又是降序的数，只检查一次就行，避免重复计算。
3. 单调数增长可控：对于绝大多数n，最小的k对应的单调数都不会太大，比如n=999，最小k是112（999*112=111888，升序），生成这个数根本花不了多少时间，绝对能在1秒内搞定。

内容的提问来源于stack exchange，提问作者Jaakko Seppälä