给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。
题目链接：https://leetcode.cn/problems/previous-permutation-with-one-swap/
# 解题思路
贪心：
- 要是替换后的数比原始排序小，则能替换的是：
arr[i] > arr[j] 且 i < j - 要使得替换后的数为最大的排序数，就要使替换的 i 尽可能靠后，因此可能最后往前变量数组，找到第一个满足
arr[i] > arr[i+1] - 再从 n-1 开始找第一个比
arr[i]小的数arr[j]，因为arr[j]是比arr[i]小的最大的数
需要注意的是可能有多个 arr[j] ，应该取下标最小的，比如：
[4,1,1,1,4] ，应取 arr[1] 与 arr[0] 交换
# 提交结果
# 代码
class Solution { | |
public int[] prevPermOpt1(int[] arr) { | |
if (arr.length < 2) return arr; | |
int n = arr.length; | |
for (int i = n - 2; i >= 0; --i) { | |
if (arr[i] > arr[i + 1]) { | |
int j = n - 1; | |
int t = arr[i]; | |
while (j > i && arr[j] >= t) { | |
--j; | |
} | |
// 可能有与 arr [j] 相等的数，则替换位置更靠前的一个 | |
int k = j - 1; | |
while (k > i && arr[j] == arr[k]) --k; | |
arr[i] = arr[k + 1]; | |
arr[k + 1] = t; | |
break; | |
} | |
} | |
return arr; | |
} | |
} |
