1. 问题描述：
给你一个正整数的数组 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 <= 100001 <= A[i] <= 10000来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/previous-permutation-with-one-swap
2. 思路分析：
① 首先需要观察交换的数字的排列存在什么特点，可以发现交换的数字都是存在逆序的特点（大多是逆序的数字与最后一个位置交换）我们可以从数组A的最后一个位置往前找第一个不满足A[i] > A[i - 1]的位置i，所以对A数组逆序遍历找到第一个单调递增的位置，比如[1,9,4,6,7]，从后往前找第一个不是单调递增的数字为4，这个时候我们找的i前一个位置的数字9就是一个可能需要交换的数字，上面的例子中数字9就可以与最后一个数字进行交换从而得到交换一次使得字典序排列比之前的排序小的最大可能排列（为什么是最后一个数字呢？因为我们是从数组A的最后一个位置开始往前找的，所以越往后面的数字是越大的所以需要交换i - 1位置与数组中的最后一个位置）
② 一开始的时候想到的①中的思路大体上是正确的，但是在某些细节上可能不对我们只需要对某些细节进行调整就ok了，比如[3,1,1,3]，我们找到的第一个交换的位置为索引为0的位置这个时候我们是不能够交换索引为0与最后一个位置的数字，因为这两个数字是相等的，所以我们找到i这个位置之后，还需要从数组A的最后一个往前找一个小于A[i]的位置，并且在找的过程中有可能是遇到中间多个数字相等的情况，比如[3,1,1,3]找到的第二个交换的位置j = 2但是这个时候发现索引为1与2的位置的数字是一样的，都是为1所以这个时候我们还需要使用一个循环寻找相邻的数字不相等的位置这样我们才能够把数字大的位置放在高位，例如[3,1,1,3]交换索引为0与索引为1的位置而不是索引为0与2的位置
③ 有的时候我们需要先写出大体上的思路然后再添加一些细节上的的东西
3. 代码如下：
from typing import List class Solution: def prevPermOpt1(self, A: List[int]) -> List[int]: n = len(A) - 1 i = n while i > 0 and A[i] >= A[i - 1]: i -= 1 # 找到第一个交换的高位上的数字 i -= 1 if i >= 0: j = n # 找到第二个A[i] > A[j]的位置j while 0 < j != i and A[i] <= A[j]: j -= 1 # 假如第二个交换的数字中相邻的数字是一样的话还要继续往前找 while j > 0 and A[j] == A[j - 1]: j -= 1 # 交换两个位置上的数字 if i != j: A[i], A[j] = A[j], A[i] return A
