1053. Previous Permutation With One Swap

O(n) time
相当于找prev_permutation，要在右边找一个小数换左边的一个大数，右边的小数要在尾部的升序序列里找
312右侧升序，从后往前找到第一个违反升序的31，再在升序序列里找『第一个』比3小的最大的数，也就是先找3的下界再往前找第一次出现的最大的数跟3交换即可

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = size(A), i = n - 1;
        while (i > 0 && A[i - 1] <= A[i]) --i;
        if (i == 0) return A;
        int j = lower_bound(begin(A) + i, end(A), A[i - 1]) - begin(A) - 1;
        j = lower_bound(begin(A) + i, begin(A) + j + 1, A[j]) - begin(A);
        swap(A[i - 1], A[j]);
        return A;
    }
};

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size(), x = n;
        for (int i = n - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                x = i; // 先从后往前找到第一个违反递减关系的数A[x]
                break;
            }
        }
        if (x == n) return A;
        int y = lower_bound(begin(A) + x + 1, end(A), A[x]) - begin(A) - 1; // 从后往前二分找到第一个小于A[x]的数A[y]
        y = lower_bound(begin(A) + x + 1, begin(A) + y + 1, A[y]) - begin(A); // 再找到第一个A[y]跟A[x]交换
        swap(A[x], A[y]);
        return A;
    }
};

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size(), x = n;
        for (int i = n - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                x = i;
                break;
            }
        }
        if (x == n) return A;
        auto y = lower_bound(begin(A) + x + 1, end(A), A[x]) - begin(A) - 1;
        while (x < y && A[y - 1] == A[y]) {
            --y;
        }
        swap(A[x], A[y]);
        return A;
    }
};