每日算法系列【LeetCode 1053】交换一次的先前排列

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

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

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

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

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