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

示例 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 {	//C++
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int i = 0, l = 0, r = 0;
        for(i = 1; i < A.size(); ++i)
        {
            if(A[i-1] > A[i])//遇到下降, 更新, l,r越靠后越好
                l = i-1, r = i;
            //后序找到小于 A[l] 的数, 但是大于 A[r]的，
            //    用更大的与 l 交换，得到更大的字典序
            else if(A[i] < A[l] && A[i] > A[r])
                r = i;
        }
        swap(A[l], A[r]);
        return A;
    }
};

class Solution:# py3
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        l, r = 0, 0
        for i in range(1,len(A)):
            if A[i-1] > A[i]:
                l, r = i-1, i
            elif A[i] < A[l] and A[i] > A[r]:
                r = i
        t = A[l]
        A[l] = A[r]
        A[r] = t
        return A