https://leetcode.cn/problems/previous-permutation-with-one-swap/
给你一个正整数数组 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] 的那个数。不难写出如下代码：
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就过不了。因此实际上是：
- 从右往左第一个小于 arr[l] 的 arr[j]
- arr[j] == arr[j-1]，那么优先选择 j - 1
- 需要 i 尽可能地大（尽可能的把低位变大，而不是高位），nums[j] 尽可能大
- 语言支持：Python3
Python3 Code:
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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
