寻找下一个更大的数 | Baeldung中文网

1. 概述

在本文中，我们将学习一个经典的算法问题：给定一个非负整数，使用相同的数字组合，找出比它大的最小整数。

如果该数字已经是当前数字集合中能组成的最大值（如 4321），则返回其本身。

这个算法在很多实际场景中都有应用，比如 LeetCode 上的题目，或者作为其他组合问题的子步骤。

2. 解题思路详解

我们以数字 12365 为例，来逐步说明算法逻辑。

✅ 步骤一：从右往左找第一个比右边小的数字 D

我们从右往左遍历数字，找到第一个比它右边数字小的位置。这个数字我们记作 D。

例如在 12365 中，从右往左看：

5 < 6 ✅
6 > 3 ❌
3 > 2 ❌
2 > 1 ❌

所以，D = 3，它的位置是倒数第 3 位。

⚠️ 如果整个数字是递减的（如 4321），那么没有下一个更大的排列，直接返回原数。

✅ 步骤二：在 D 的右侧找一个最小但比 D 大的数字 S

继续在 3 的右侧找最小但比 3 大的数字，即 5。

我们记这个数字为 S = 5。

✅ 步骤三：交换 D 和 S

交换 3 和 5，得到 12563。

✅ 步骤四：将 S 后面的所有数字反转

最后，将 S 后面的所有数字反转，使这部分变成最小可能的排列。

将 63 反转成 36，最终结果是 12536。

✅ 最终结果：12536 是比 12365 更大的最小数字。

3. 算法实现（Java 伪代码）

algorithm findNextHigherNumber(str, n):
    // INPUT
    //   str = The string of the given number
    //   n = The length of the string
    // OUTPUT
    //   str = The string of the next higher number

    for i <- n - 1 to 1:
        if str[i] > str[i - 1]:
            break

    if str[i] > str[i - 1]:
        D <- str[i - 1]
        S <- str[i]
        for j <- i + 1 to n - 1:
            if str[j] > D and str[j] < S:
                S <- str[j]
        
        Swap the digits S and D
        Reverse the sequence of digits after the digit S
        return str
    else:
        return str

4. 时间复杂度分析

我们来分析每一步的时间开销：

步骤	描述	时间复杂度
第一步	找到 D	O(n)
第二步	找到 S	O(n)
第三步	交换 D 和 S	O(1)
第四步	反转 S 后的数字	O(n)

✅ **总时间复杂度：O(n)**，其中 n 表示数字的位数。

这已经是一个非常高效的解法，适用于大多数实际应用场景。

5. 总结

本文我们介绍了一个经典的算法问题：如何找出一个数字的“下一个更大”的排列。

我们通过四个清晰的步骤实现了该算法：

找到第一个比右边小的数字 D
在 D 右侧找到最小但比 D 大的数字 S
交换 D 和 S
反转 S 后面的部分

✅ 该算法时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。

⚠️ 踩坑提醒：实现时注意边界条件，比如数字全降序的情况（应直接返回原数），或者多个相同数字时要找“最小但比 D 大”的那个 S。

这个算法在刷题和实际工程中都非常实用，建议多加练习，熟练掌握。

Persistence

REST

Security