问题描述
给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i]和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。
如果无法这么操作，就请返回原数组。
示例
输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1
输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列
输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7
输入：arr = [3,1,1,3]
输出：[1,3,1,3]
解题思路
核心思路：贪心
首先，需要理解题目意思：“字典序排列大小”，可以直接把数组看成一个多位整数，比较大小即可；
其次，怎么得出这个小于原序列的最大排列？尽量保证前面的数不变，让后面的数进行交换，比如序列[3,3,3,2,1]。
初步的思路：
从后往前遍历原数组arr，找到整数a[i]后面比它小的最大的第一个数，如果能找到，进行交换并结束。
优化：
- 从后往前遍历原数组
arr，如果a[i] > a[i+1]，再去寻找交换的整数。
因为能遍历到a[i]，说明他后面的数都找不到后面比他们小的数，也就是说后面的数是有序且递增的； - 寻找整数
a[i]后面与之交换的整数的时候，可以直接从后往前寻找（因为从后往前是递减的），直到寻找到第一个必它小的数（保证这个数是比它小同时是最大的数），并且这个数需要尽量的靠近a[i]（防止有连续的数）。
例如：[3,1,1,3]的输出是[1,3,1,3]，3和第一个1进行交换。
代码示例（JAVA）
class Solution {
public static int[] prevPermOpt1(int[] arr) {
int length = arr.length;
for (int i = length - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
int j = length - 1;
while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
j--;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
break;
}
}
return arr;
}
}
