题目链接
难度：中等 类型： 贪心算法
给你一个正整数的数组 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
解题思路
为了使交换后的数小于原数又尽可能的大，所以更希望靠后的数字交换
经过找规律发现，从后往前第一个递增的数就是要交换的数a，该数右边一定有一个比它小，找小的里面最大的那个跟它换，会使交换后的数尽可能的大，这个数字是从后往前第一个小于a的数b
例如示例3，从后往前第一个递增的数是9，从后往前第一个小于9的数是7，所以两者交换
有一种特殊的情况，即示例4，不仅要找到b，还要找到离a最近的b，代码实现起来很简单
代码实现
class Solution(object):
def prevPermOpt1(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
n = len(A)
right = n-1
for i in range(n-1,0,-1):
if A[i-1] > A[i]:
j = n-1
while A[j]>=A[i-1] or A[j] == A[j-1]:
j -= 1
A[j], A[i-1] = A[i-1], A[j]
break
return A
