题目：1053.交换一次的先前排列

思路：

对于数组int[] A = [1,9,4,6,7]：

1、左边是高位，右边是低位;

2、替换后，左边被替换的数字势必变小

为了满足题意，使替换后的数字尽可能大，需要尽量替换右侧数字，

即：找到最右侧逆序位置L，使A[L] > A[L + 1]，若找到一定有解，且替换A[L]位置为最优解。

遍历A[L]右侧的数字，使得A[R]最大且满足A[L] > A[R]。

java 代码：

    public static int[] prevPermOpt1(int[] A) {
        int L = -1;
        int R = -1;

        // 找到最右逆序
        for(int i = A.length - 2 ; i >= 0 ; i--) {
            if (A[i + 1] < A[i]) {
                if (L == -1) {
                    L = i;
                }
                R = L + 1;
                break;
            }
        }

        // 找到L右边小于A[L]的最大值所在位置R
        for(int j = L + 1 ; L >= 0 &&j < A.length ; j++) {
            if(A[j] < A[L] && A[j] > A[R]){
                R = j;
            }
        }

        // 交换位置
        if(L >= 0 && R >= 0){
            int tmp = A[L];
            A[L] = A[R];
            A[R] = tmp;
        }
        return A;
    }


    public static void main(String[] args){
        int[] arr = {3,1,1,3};
        System.out.println(Arrays.toString(prevPermOpt1(arr)));
    }

[3, 1, 2]