FInd下一个相同数字的最小数字Python

Question

我在Codewars上遇到了这个挑战：https ://www.codewars.com/kata/next-smaller-number-with-the-same-digits

它接受一个非常大的整数。并返回具有相同数字的下一个最小整数，-1如果不存在则返回。我尝试用蛮力尝试此操作，找到所有排列并找到最接近的排列。这显然效率不高，并导致超时。

什么是有效的方法？

Answer 1

1. 从右边开始，找到右边至少有一个小数位的第一个数字。我们将其称为X。
2. 然后找到X右边最大的数字，该数字小于X。我们将其称为Y。
3. 交换X和Y。这使数字更小。
4. 然后按降序对Y右边的所有数字进行排序。这样可以使数字尽可能大，而不必使其大于原始数字。

例如：

1262347  // original number
  ^  ^
  X  Y

1242367  // after the swap
  ^  ^
  Y  X

1247632  // after sorting digits to the right of Y
  ^
  Y