题目描述

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

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

样例

输入：[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。

说明

• 1 <= A.length <= 10000
• 1 <= A[i] <= 10000

算法

(贪心) $O(n)$

1. 假设最后一个位置后边为正无穷，则我们考虑这样的连续三个位置 (i, i + 1, i + 2)，满足 A[i] > A[i + 1] 且 A[i + 1] <= A[i + 2]，将从后向前第一个这样的位置 i，记为 x。
2. 如果 x 不存在，则说明数组是单调不降的，则不存在更小的排列。
3. x 存在，则被交换的一个位置必定是 x，且另一个交换的位置 y 为大于 x 且数字小于 A[x] 的最大值。
4. 显然，如果 x 存在，我们不可能交换 x 之前的某个位置。显然，交换时，需要找 x 之后尽可能大的数字，但不能大于等于 x。

时间复杂度

• 每个数字最多遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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

        A.push_back(INT_MAX);

        int x = -1;

        for (int i = n - 2; i >= 0; i--)
            if (A[i] > A[i + 1] && A[i + 1] <= A[i + 2]) {
                x = i;
                break;
            }

        A.pop_back();

        if (x == -1)
            return A;

        int y = x + 1;
        for (int i = x + 1; i < n; i++)
            if (A[i] < A[x] && A[y] < A[i])
                y = i;

        swap(A[x], A[y]);

        return A;
    }
};