LeetCode 1053. 交换一次的先前排列

798236606

传送门：https://leetcode-cn.com/problems ... tion-with-one-swap/

分析：
1.交换的两个数必然是前大后小，这样才能产生字典序更小的序列
2.被选择的大数越往后越好，因为越往后对字典序的下降影响越小
3.被选择的小数越大越好（相同值取最左），对字典序下降影响小
4.大数与小数必须先固定一方，由于大数靠前影响大，先固定大数

思路：
1.从后往前遍历每一数，若在这个数之后有比它小的数，它就成为大数固定下来。
2.从大数后遍历每一数，若这个数是小于大数的最大数，它就成为小数固定下来。
3.大小数交换， 得答案。

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size();

        for (int i = n - 2; i >= 0; --i)
        {
            int maxid = -1, maxn = -1;

            for (int j = i + 1; j < n; ++j)
                if (A[i] > A[j] && maxn < A[j])
                {
                    maxid = j;
                    maxn = A[j];
                }

            if (maxid == -1) continue;

            swap(A[i], A[maxid]);
            break;
        }

        return A;
    }
};