解决方案
步骤
1
如果从右往左一直递减，则无法交换，直接返回
2
找到从右往左 第一个 打破递减规律的，作为左边的要交换的数
3
找到从右往左 第一个 小于 选中的左边的数的，作为右边要交换的数
4
如果找到的右边的数的左边有跟它一样的数，那么要选择最左边跟它等值的，作为右边要交换的数
分析
整个题就是要找两个数字进行交换，所以我们找找规律
递减性
观察
样例中，成功交换的两个数，貌似都是 从右往左 在打破递减规律时，那个位置要互换
[3, 2, 1]
^ ^
2 是 从右往左 第一个 不递减的[1, 1, 5] 没有不递减的，所以互换没收益
[1, 9, 4, 6, 7]
^ ^
9 是 从右往左 第一个 不递减的[3, 1, 1, 3] ^ ^ 3 是 从右往左 第一个 不递减的 然而右边要交换的 不是最右边的 3，而是 1 看来，这块需要之后推理找规律
推测
根据上面的观察，我们可以假设
交换的 两个数的左边的那个数，一定是 从右往左 打破递减规律的 第一个数
右边需要交换的数字
观察
当我们找到 要交换的左边的那个数字时，可能会跟 最右侧的数字 产生三种情况
情况 1
右边的 小于 左边的
比如 413 换成 314，还不错
情况 2
右边的 等于 左边的
比如 313 换成 313
这样不行，因为题目要求交换后，要小于 交换前的数
情况 2
右边的 大于 左边的
比如 213 换成 312
这样也不行，因为题目要求交换后，要小于 交换前的数
推测
所以得从右边往左边找，第一个 小于 左边那个数字的
也就是说 313 的右边得选 1， 也就是 换成 133
213 的右边也得选 小于 2 的 1，换成 123
另外一个特殊情况
观察
如果我们的数据是 3114，
依照我们上面的规则，那就是 左边的要交换的是 3。
右边的要交换的是 十位数的 1，
那么我们会得到 1134
然而，如果左边跟 百位数的 1 交换，会更好
会得到 1314，比 1134 要大，且小于 3114
推测
所以我们猜测，当确定右边的数字后，如果这个数字的左边有一样的，那么就选择最左边一样的那个
Java 代码
Runtime: 0 ms
Memory Usage: 39.7 MB
Beats 100.00% of java submissions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public class Solution { public int[] prevPermOpt1(int[] A) { // 1. 边界情况处理 if (A.length == 1) { return A; } // 2. 找左边要交换的位置 int left = A.length - 2; while (left >= 0) { if (A[left] > A[left + 1]) { break; } left--; } // 2.1 如果一直递减 if (left < 0) { return A; } // 3. 找右边 第一个小于 left 的值 int right = A.length - 1; while (A[right] >= A[left]) { right--; } // 4. 向左错位，如果 right 的左边 跟 right 一样 int rightValue = A[right]; while (A[right] == rightValue) { right--; } right++; // 5. 交换 int temp = A[left]; A[left] = A[right]; A[right] = temp; return A; }}
Java Script 代码
Runtime: 100 ms
Memory Usage: 38.8 MB
Beats 83.08% of javascript submissions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public class Solution { public int[] prevPermOpt1(int[] A) { // 1. 边界情况处理 if (A.length == 1) { return A; } // 2. 找左边要交换的位置 int left = A.length - 2; while (left >= 0) { if (A[left] > A[left + 1]) { break; } left--; } // 2.1 如果一直递减 if (left < 0) { return A; } // 3. 找右边 第一个小于 left 的值 int right = A.length - 1; while (A[right] >= A[left]) { right--; } // 4. 向左错位，如果 right 的左边 跟 right 一样 int rightValue = A[right]; while (A[right] == rightValue) { right--; } right++; // 5. 交换 int temp = A[left]; A[left] = A[right]; A[right] = temp; return A; }}
Python 代码
Runtime: 140 ms
Memory Usage: 14.3 MB
Beats 99.82% of javascript submissions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def prevPermOpt1(self, A: List[int]) -> List[int]: # 1. 边界情况处理 if len(A) == 1 : return A # 2. 找左边要交换的位置 left = len(A) - 2 while left >= 0 : if A[left] > A[left + 1] : break left -= 1 else : # 2.1 如果一直递减 return A # 3. 找右边 第一个小于 left 的值 right = len(A) - 1 while A[right] >= A[left] : right -= 1 # 4. 向左错位，如果 right 的左边 跟 right 一样 right_value = A[right] while (A[right] == right_value) : right -= 1 right += 1 # 5. 交换 A[left], A[right] = A[right], A[left] return A
