给定一个数字，找到与原始数字具有完全相同的数字组的下一个更高的数字

我刚刚搞砸了一次面试，并且在面试问题上几乎取得了零进展。

给定一个数字，找到下一个具有完全相同的数字 一组数字作为原始数字。例如：给出 38276 返回 38627

我想首先找到小于个位的第一个数字（从右侧）的索引。然后我会旋转子集中的最后一位数字，使其成为由相同数字组成的下一个最大数字，但被卡住了。

面试官还建议尝试一次交换一位数字，但我无法弄清楚算法，只是盯着屏幕看了 20-30 分钟。不用说，我想我必须继续找工作。

你可以这样做O(n) (where n是位数），如下所示：

从右边开始，找到第一对数字，使得左边的数字小于右边的数字。让我们用“digit-x”来引用左边的数字。在数字 x 的右侧找到比数字 x 更大的最小数字，并将其放在紧邻数字 x 的左侧。最后，将剩余的数字按升序排序 - 因为它们已经在下降顺序，你所需要做的就是颠倒它们（除了数字-x，它可以放在正确的位置O(n)).

一个例子会让这一点更清楚：

123456784987654321
start with a number

123456784 987654321
         ^the first place from the right where the left-digit is less than the right  
         Digit "x" is 4

123456784 987654321
              ^find the smallest digit larger than 4 to the right

123456785 4 98764321
        ^place it to the left of 4

123456785 4 12346789
123456785123446789
         ^sort the digits to the right of 5.  Since all of them except 
         the '4' were already in descending order, all we need to do is 
         reverse their order, and find the correct place for the '4'
  

正确性证明：

让我们使用大写字母来定义数字字符串，使用小写字母来定义数字。语法AB means “字符串的连接A and B". <是字典排序，与数字字符串长度相等时的整数排序相同。

我们原来的数字 N 的形式为AxB, where x是一位数并且B是降序排列的。
我们的算法找到的数字是AyC, where y ∈ B是最小的数字> x （它必须存在，因为方式x已选择，见上文）, and C是升序排列的。

假设有一些数字（使用相同的数字）N'这样AxB < N' < AyC. N'必须开始于A否则它不能落在它们之间，因此我们可以将其写成以下形式AzD。现在我们的不平等是AxB < AzD < AyC，这相当于xB < zD < yC其中所有三个数字字符串都包含相同的数字。

为了实现这一点，我们必须x <= z <= y。自从y是最小的数字> x, z不能在他们之间，所以要么z = x or z = y. Say z = x。那么我们的不平等是xB < xD < yC， 意思是B < D两者都在哪里B and D具有相同的数字。然而，B 是降序排序的，所以有is没有比它大的数字的字符串。因此我们不能有B < D。按照相同的步骤，我们看到如果z = y，我们不能有D < C.

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