# LeetCode-1053. Previous Permutation With One Swap

## LeetCode-1053. Previous Permutation With One Swap

Posted by Jae on November 16, 2019

### 1、题目

Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]). If it cannot be done, then return the same array.

Example 1:

Input: [3,2,1] Output: [3,1,2] Explanation: Swapping 2 and 1. Example 2:

Input: [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation. Example 3:

Input: [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swapping 9 and 7. Example 4:

Input: [3,1,1,3] Output: [1,3,1,3] Explanation: Swapping 1 and 3.

Note:

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

### 2、思路

• 步骤1： 首先从后往前找到第一个满足比其后数字大的数，如果不存在，说明该数无法通过交换来减小，算法结束，否则转步骤2；
• 步骤2: 从步骤1中找到的数往后找比该数小的最大数位置；
• 步骤3: 交换步骤1和步骤2找的两个索引上对应的数；

### 3 实现

public class Solution {
public int[] prevPermOpt1(int[] A) {
int N = A.length;
int s1 = -1;
for (int i = N-2; i >= 0; i--){
if (A[i] > A[i+1]){
s1 = i;
break;
}
}
if (s1 == -1) return A;
int s2 = s1 + 1;
// 这里使用的是查找最大值次大值方法
for (int j = s1 + 2; j < N; j++){
if (A[j] < A[s1] && A[j] > A[s2]){
s2 = j;
}
}
int t = A[s1];
A[s1] = A[s2];
A[s2] = t;

return A;
}
}


< script src = " / js / bootstrap.min.js " >