题目描述 [ 交换一次的先前排列]

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

如果无法这么操作，就请返回原数组。

示例

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

解题思路

从数组的末尾开始往前遍历，保证遍历过的子数组从后往前降序排列，找到第一个不满足降序要求的数字。例如对于数组[1,9,4,6,7]，[7,6,4]降序排列，因此找到的第一个数字是9。然后将该数字与它后面小于它的最大数字交换即可。

代码

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        for(int i=A.size()-2; i>=0; i--){
            if(A[i]>A[i+1]){
                for(int j=A.size()-1;j>i;j--){
                    if(A[j]<A[i]){
                        swap(A[i], A[j]);
                        return A;
                    }
                }
            }
        }
        return A;
    }
};