leetcode 1053 交换一次的先前排列

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

思路:

从右往左找，找到第一个非递增的位置

然后从左往右，找到比上面的小，但是比其他的大的位置

class Solution:
    # def prevPermOpt1(self, A: List[int]) -> List[int]:
    def prevPermOpt1(self, A):
        pos1 = 0
        for i in range(len(A) - 2, -1, -1):
            if A[i] > A[i + 1]:
                pos1 = i
                break
        pos2 = 0
        current_max = 0
        for i in range(pos1 + 1, len(A)):
            if current_max < A[i] < A[pos1]:
                current_max = A[i]
                pos2 = i
        A[pos1], A[pos2] = A[pos2], A[pos1]
        return A