【leetcode刷题】T184-交换一次的先前排列

示例 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

class Solution(object):
    def prevPermOpt1(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        if len(A) < 1:
            return A
        i = len(A) - 2
        while i >= 0:
            if A[i] > A[i+1]:
                # 直接和最后一个元素比较
                if A[i] > A[-1]:
                    A[i], A[-1] = A[-1], A[i]
                else:
                    # 找到大于A[i]的第一个元素的前一个元素
                    j = i+2
                    while A[i] > A[j]:
                        j += 1
                    j -= 1
                    # 如果相邻的有重复元素，则必须找到重复元素第一个
                    while A[j] == A[j-1]:
                        j -= 1
                    A[i], A[j] = A[j], A[i]
                break
            i -= 1
        return A