# 交换一次的先前排列 - Previous Permutation With One Swap

【字典序】

### Example:

``````输入：[3,2,1]

``````

``````输入：[1,1,5]

``````

``````输入：[1,9,4,6,7]

``````

``````输入：[3,1,1,3]

``````

1. `1 <= A.length <= 10000`
2. `1 <= A[i] <= 10000`

### Analysis

• 由于\$A[i]>A[i+1]\$，必能构造比当前字典序小的序列
• 由于逆序查找，交换`A[i]`为最优解

• 由于 \$A[j] < A[]i]\$, 交换 `A[i]``A[j]` 后的序列字典序一定小于当前字典序
• 由于 `A[j]` 是满足关系的最大的最左的，因此一定是满足小于关系的交换后字典序最大的

[3, 1, 1, 3] => [1, 3, 1, 3]

[3, 1, 2, 3] => [2, 1, 3, 3]

[4, 1, 2, 3] => [3, 1, 2, 4]

### Solution 【字典序】 ( 1ms)

 `````` 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 `````` ``````class Solution { public int[] prevPermOpt1(int[] A) { int len = A.length; int curMax = -1; int index = -1; boolean hasResult = false; for (int i = len - 2; i >= 0; i--) { if (A[i+1] < A[i]) { // 此处逆序，需要移动A[i] for (int j = i + 1; j < len; j++) { // 寻找与 A[i] 交换的位置 if (A[i] > A[j]) { // 必须满足 A[i] > A[j]，否则不能满足交换后的字典序小于原始字典序 hasResult = true; if (A[j] > curMax) { curMax = A[j]; index = j; } } } if (hasResult) { int tmp = A[i]; A[i] = A[index]; A[index] = tmp; return A; } } } return A; } } ``````