1053. 交换一次的先前排列

1053. 交换一次的先前排列

给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。

题目理解：

1、比原序列字典序要小，则序列中必须存在逆序，否则无法操作；
2、序列中存在逆序的情况下，可以有多种交换方法，需要取交换后字典序最大的那个；
3、如果要取最小可能序列，应该怎么做？

示例 1：

输入：[3,2,1]
输出：[3,1,2]
解释：交换 2 和 1
 
示例 2：

输入：[1,1,5]
输出：[1,1,5]
解释： 这已经是最小排列

示例 3：

输入：[1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7
 
示例 4：

输入：[3,1,1,3]
输出：[1,3,1,3]
解释：交换 1 和 3

vector<int> prevPermOpt1(vector<int>& A) {
    int size = A.size();
    if(size <= 1) return A;
    int big_pos = -1;
    int big = A[size-1];
    //从后往前寻找第一个逆序的位置及其值
    for(int i = size-1; i > 0; i--){
        if(A[i] < A[i-1]){
            big_pos = i-1;
            big = A[i-1];
            break;
        }
    }
    //如果位置没有更新，代表无逆序，直接返回A
    if(big_pos == -1) return A;
    int small = A[big_pos+1];
    int small_pos = big_pos+1;
    //从找到的逆序位置往后寻找小于该值的最左最大的值
    for(int j = big_pos+1; j < A.size(); j++){
        if(A[j] > small && A[j] < big){
            small = A[j];
            small_pos = j;
        }
    }
    swap(A[big_pos], A[small_pos]);
    return A;
}