题目描述
给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。
示例
输入：arr = [3,2,1]
输出：[3,1,2]
输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
输入：arr = [3,1,1,3]
输出：[1,3,1,3]
输入：arr = [3,1,2,3]
输出：[2,1,3,3]
输入：arr = [4,1,2,3]
输出：[3,1,2,4]
实现逻辑
这道题目的关键是 按字典序排列小于 A 的最大可能排列， 那么有
- 对当前序列进行逆序查找，找到第一个降序的位置 i，使得 A[i]>A[i+1]
由于 A[i]>A[i+1]A[i]>A[i+1]，必能构造比当前字典序小的序列
由于逆序查找，交换 A[i] 为最优解 - 寻找在 A[i] 右边小于 A[i] 的最大的数字 A[j]
由于 A[j] < A[i], 交换 A[i] 与 A[j] 后的序列字典序一定小于当前字典序
由于 A[j] 是满足关系的右边最大的，因此一定是满足小于关系的交换后字典序最大的
实现代码
package leetcode;
public class Solution1053 {
public static int[] prevPermOpt1(int[] arr) {
int len = arr.length;
int maxJ = -1;
int indexJ = -1;
boolean hasResult = false;
for(int i=len-2; i>=0; i--){
if(arr[i+1]<arr[i]){
//arr[i]为逆序结尾处，为待交换元素
for(int j=i+1; j<len; j++){
//寻找与 arr[i] 交换的位置
if(arr[i]>arr[j]){
// 必须满足 arr[i] > arr[j]，否则不能满足交换后的字典序小于原始字典序
hasResult = true;
if(arr[j]>maxJ){
maxJ = arr[j];
indexJ = j;
}
}
}
if(hasResult){
int tmp = arr[i];
arr[i] = arr[indexJ];
arr[indexJ] = tmp;
return arr;
}
}
}
return arr;
}
public static void main(String[] args) {
int arr[] = new int[]{1,9,4,7,6};
int result[]= prevPermOpt1(arr);
for(int i=0; i<result.length; i++){
System.out.println(result[i]);
}
}
}
联系作者
微信公众号
xiaomingxiaola
（BossLiu）
QQ群
58726094
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 384276224@qq.com
