求优化：给定整数寻找同数位下一个更大数的算法

给定整数，找出由相同数位组成的下一个更大数，若无则返回-1。函数预期行为示例：

• next_bigger(13) → 31
• next_bigger(201) → 210
• next_bigger(2017) → 2071
• next_bigger(10) → -1
• next_bigger(587) → 758

原实现用itertools.permutations()生成所有排列后排序查找，但该方法时间复杂度为O(n!)，对于位数较多的数（如10位及以上）完全不可行。原代码如下：

import itertools

def next_bigger(n):
    x = list(itertools.permutations(str(n), len(str(n))))
    lst = [int(''.join(x[i])) for i in range(0, len(x))]
    lst.sort(reverse=True)
    if n == lst[0]:
        return -1
    for i in range(0, len(lst)):
        if lst[i + 1] == n:
            return lst[i]

尝试过转集合去重、仅保留大于原数n的值，但本质上仍未解决生成全排列带来的高开销问题。

优化方案：使用经典「下一个排列」算法 #

该算法时间复杂度为O(n)，空间复杂度为O(n)，核心是通过数位直接操作找到下一个更大数，无需生成所有排列。步骤如下：

1. 将整数转为字符列表（方便数位修改）
2. 从右向左找第一个升序对：找到最大的索引i，使得digits[i] < digits[i+1]。若找不到，说明当前数是最大排列，返回-1。
3. 从右向左找第一个更大的数位：找到最大的索引j，使得digits[j] > digits[i]。
4. 交换i和j位置的数位：此时i右侧的数位为降序排列。
5. 反转i右侧的数位：将i右侧数位反转，得到最小的升序排列，最终组合成原数的下一个更大数。

实现代码 #

def next_bigger(n):
    digits = list(str(n))
    length = len(digits)
    
    # 找第一个digits[i] < digits[i+1]的索引i
    i = length - 2
    while i >= 0 and digits[i] >= digits[i+1]:
        i -= 1
    if i == -1:
        return -1  # 不存在更大的数
    
    # 找第一个比digits[i]大的数位j
    j = length - 1
    while digits[j] <= digits[i]:
        j -= 1
    
    # 交换i和j的数位
    digits[i], digits[j] = digits[j], digits[i]
    
    # 反转i右侧的数位，得到最小升序排列
    digits[i+1:] = digits[i+1:][::-1]
    
    result = int(''.join(digits))
    return result if result > n else -1

测试验证 #

• next_bigger(13) → 31 ✔️
• next_bigger(201) → 210 ✔️
• next_bigger(2017) → 2071 ✔️
• next_bigger(10) → -1 ✔️
• next_bigger(587) → 758 ✔️
• next_bigger(111) → -1 ✔️
• next_bigger(1234) → 1243 ✔️

该算法彻底规避了全排列的高开销，适合处理任意位数的整数输入。

内容的提问来源于stack exchange，提问作者Wenderer