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