给定一个数字，找到下一个与原始数字具有完全相同数字集的更高数字。
给定一个数字，找到下一个与原始数字具有完全相同数字集的更高数字。
我刚刚进行的面试非常糟糕，而且我的面试问题几乎没有任何进展。
给定一个数字，找出下一个具有与原始数字完全相同的数字集的更高数字。例如：给定38276返回38627
我想先找到数字集中第一个（从右侧）小于个位数的数字的索引。然后我会旋转子集中的最后几位，以形成由相同数字组成的下一个更大的数字，但我卡住了。
面试官还建议尝试一次交换一个数字，但我想不出算法，只是看着屏幕发呆了20-30分钟。不用说，我认为我必须继续找工作了。
一道几乎相同的问题在 Code Jam 上出现了，这里有一个解决方案：
http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1
下面是一个例子总结的方法：
34722641
A. 把数字序列分成两半，使右边的部分尽可能地长，同时保持下降顺序：
34722 641
（如果整个数字序列是下降的，那么没有比增加数字更大的数字。）
此时，你知道已经没有以左半部分开头的更大的数字，因为剩下的数字已经用在右半部分尽可能地大了。
B.1. 选择第一序列的最后一位数字：
3472(2) 641
B.2. 找到第二序列中比它大的最小数字：
3472(2) 6(4)1
你正在找到可能的最小增量来增加左半部分。
B.3. 交换它们：
3472(2) 6(4)1 -> 3472(4) 6(2)1 -> 34724 621
C. 把第二个序列按递增顺序排序：
34724 126
D. 完成了！
34724126
你把数字分成了两个部分，以至于你知道没有更大的与同样的左半部分相同的数字。你通过最小化增加左半部分的方法增加了它，并使剩下的右半部分尽可能小，因此你可以确定这个新数字是用相同数字集合可以得到的最小更大数字。
你可以按以下方式以 O(n)（其中 n 为数字位数）完成它:
从右侧开始，找到第一个数字对，其中左侧的数字小于右侧的数字。 我们用“数位-x”来指代左侧数字。在数位-x右侧找到比数位-x大的最小数字，紧挨着放在数字-x左侧。最后，以升序排序剩余数字-因为它们已经按降序排列，所以你只需要将它们反转（降序变为升序），除数字-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 是最小的数字，且 y > x (根据选择 x 的方式，它必须存在)，C 按升序排序。
假设有一个数字（使用相同的数字） N'，使得 AxB < N' < AyC。 N' 必须以 A 开头，否则它就不能在它们之间，所以我们可以写成 AzD 的形式。现在我们的不等式是 AxB < AzD < AyC，它等价于在所有三个数字字符串包含相同数字的情况下 xB < zD < yC。
为了使其成立，我们必须有 x ≤ z ≤ y。 由于y是最小数字 x > y，所以z不能在它们之间，因此z = x 或 z = y。设 z = x。 那么我们的不等式是 xB < xD < yC，这意味着 B < D，其中 B 和 D 有相同的数字。然而，B是按降序排序的，因此没有比它大的字符串。 因此，我们不能有 B < D。类似地，如果 z = y，则不能有D < C。
因此，N'不存在，这意味着我们的算法正确找到了下一个更大的数字。