# 1053. 交换一次的先前排列)
### 题目地址(1053. 交换一次的先前排列)
### 题目描述
```
给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1
示例 2：
输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列
示例 3：
输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7
提示：
1 <= arr.length <= 104
1 <= arr[i] <= 104
```
### 前置知识
*
### 公司
* 暂无
### 思路
题目大意为：找到满足 i < j and arr\[i] > arr\[j] 的最大值。
也就是说要将 arr\[i] 变小的情况下， 变得尽可能地大。为了满足这个条件， 需要 i 尽可能地大（尽可能的把低位变小，而不是高位），因此需要从大到小枚举第一个在右侧有较小值的 i。
找到 i 之后，就需要找 j 了。nums\[j] 是右侧最大满足 nums\[j] < nums\[i] 的那个数。不难写出如下代码：
```py
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
l = -1
for i in range(len(arr)-1, -1, -1):
if arr[i-1] > arr[i]:
l = i - 1
break
if l == -1: return arr
ans = 0
r = -1
for i in range(l+1, len(arr)):
if arr[i] < arr[l] and arr[i] > ans:
ans = arr[i]
r = i
if r == -1:
return arr
arr[l], arr[r] = arr[r], arr[l]
return arr
```
实际上我们可以进一步优化常数时间，因为找 l 的过程我们有这样的信息：l 右侧是单调不递减的，因此最大的就是最后一个元素。
那么我们可以直接将数组最后一个当成 j 么？
不能！考虑 nums\[j] 可能大于等于 nums\[i]。比如这个 case \[3,1,1,3]，我们预期是 \[1,3,1,3] 而不是 \[3,1,1,3]。
那是不是从右向左找到第一个小于 nums\[j] 的就可以了？
不是！还是上面的 case就过不了。因此实际上是：
1. 从右往左第一个小于 arr\[l] 的 arr\[j]
2. arr\[j] == arr\[j-1]，那么优先选择 j - 1
### 关键点
* 需要 i 尽可能地大（尽可能的把低位变大，而不是高位），nums\[j] 尽可能大
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
l = -1
for i in range(len(arr)-1, -1, -1):
if arr[i-1] > arr[i]:
l = i - 1
break
if l == -1: return arr
for i in range(len(arr)-1, l, -1):
if arr[i] < arr[l] and arr[i] != arr[i-1]:
r = i
break
if r == -1:
return arr
arr[l], arr[r] = arr[r], arr[l]
return arr
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
