【leetcode】1053. Previous Permutation With One Swap

题目如下：

解题思路：要找出字典序小于自己的最大值，方法如下：从后往前遍历A，对于任意一个A[i]，在[i+1,A.length]区间内找出比自己小的最大值，如果能找到这样的值，则这两个元素交换，交换之后的A即为字典序小于自己的最大值。怎么找出[i+1,A.length]区间内找出比自己小的最大值？可以把区间内所有的值存入有序的数组中，通过二分查找即可。

代码如下：

class Solution(object):

    def prevPermOpt1(self, A):

        """

        :type A: List[int]

        :rtype: List[int]

        """

        import bisect

        dic = {}

        val_list = []

        for i in range(len(A)-1,-1,-1):

            inx = bisect.bisect_left(val_list,A[i])

            inx -= 1

            if inx >= 0 and inx < len(val_list):

                A[i], A[dic[val_list[inx]]] = A[dic[val_list[inx]]], A[i]

                break

            if A[i] not in dic:

                bisect.insort_left(val_list,A[i])

            dic[A[i]] = i

        return A