Previous Permutation With One Swap
找字典序上, 当前数组前一位的permutation. 这个题和next permutation是一套题. 算法就是从后向前找到第一个递减的数, 然后从后网前找到第一个递增的数即可.
class Solution {
public int[] prevPermOpt1(int[] A) {
int n = A.length;
int j = n - 2;
while(j >= 0 && A[j] <= A[j + 1])
j--;
if(j == -1) // sorted
return A;
int max = A[j+1];
int maxIndex = j+1;
for(int i = n - 1; i > j; i--) {
if(max < A[i] && A[i] < A[j]){
max = A[i];
maxIndex = i;
}
}
int tmp = A[j];
A[j] = A[maxIndex];
A[maxIndex] = tmp;
return A;
}
}