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;
    }
}