您可以这样输入O(n)（n位数是）：

从右边开始，找到第一个数字对，以使左边的数字小于右边的数字。让我们用“ digit-x”来指代左数字。在数字-x的右边找到大于数字-
x的最小数字，并将其放在数字-x的左侧。最后，将其余数字按升序排序-由于它们已经按 降序 排列，因此您要做的就是将它们反转
（保存digit-x，可以将其放置在中的正确位置O(n)）。

一个示例将使这一点更加清楚：

123456784987654321
以数字开头

123456784 987654321
         ^左数小于右数的从右到右的第一位  
         数字“ x”为4

123456784 987654321
              ^在右侧找到大于4的最小数字

123456785 4 98764321
        ^将其放在4的左侧

123456785 4 12346789
123456785123446789
         ^将数字右边的5排序。因为除 
         “ 4”已经按降序排列，我们要做的就是 
         颠倒顺序，找到正确的'4'位置

正确性证明：

让我们用大写字母定义数字字符串，并用小写字母表示数字。语法的AB含义是 “字符串A和B” 的串联。
<是字典顺序，当数字字符串长度相等时，它与整数顺序相同。

我们的原始数字N的形式为AxB，其中x是一位数字，并B以降序排列。
我们的算法找到的数字是AyC，其中y ∈ B是最小数字> x （由于x选择的方式而必须存在，请参见上文），并且C以升序排序。

假设有一些数字（使用相同的数字）N'使得AxB < N' < AyC。
N'必须以开头，A否则它不能落在它们之间，因此我们可以将其编写为形式AzD。现在我们的不等式是AxB < AzD < AyC，它等于xB < zD < yC三个数字字符串都包含相同数字的地方。

为了使这一点成为现实，我们必须有x <= z <= y。由于y是最小数字> x，z所以不能在它们之间，所以z = x或z = y。说z = x。然后我们的不平等xB < xD < yC，这意味着B < D其中两个B与D具有相同的数字。然而，B是降序排序，所以
是 没有字符串与比它大的数字。因此我们不能拥有B < D。遵循相同的步骤，我们看到if z = y不能拥有D < C。

因此N'不存在，这意味着我们的算法正确找到了下一个最大的数字。