给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：[3,2,1] 输出：[3,1,2] 解释： 交换 2 和 1
示例 2：
输入：[1,1,5] 输出：[1,1,5] 解释： 这已经是最小排列
示例 3：
输入：[1,9,4,6,7] 输出：[1,7,4,6,9] 解释： 交换 9 和 7
示例 4：
输入：[3,1,1,3] 输出：[1,1,3,3]
提示： 1 <= A.length <= 10000 1 <= A[i] <= 10000
class Solution { public int[] prevPermOpt1(int[] A) { //int[] array = A; int index = 0; int max_index = 0; //如果是顺序则直接返回 boolean flag = true; for(int i = 0; i < A.length - 1; i++){ if(A[i] <= A[i+1]){ flag = false; }else{ flag = true; break; } } if(!flag){ return A; } //如果是逆序，则最后两数交换 boolean flag2 = true; for(int i = 0; i < A.length - 1; i++){ if(A[i] >= A[i+1]){ flag2 = false; }else{ flag2 = true; break; } } if(!flag2){ swap(A, A.length - 1, A.length - 2); return A; } //非顺序，首先从左遍历找到最后一个大于右边的数 for(int i = 0; i < A.length - 1; i++){ if(A[i] > A[i+1]){ index = i; } } //找index之后，最大数对应的索引 int max = -1; for(int i = index + 1; i < A.length; i++){ if(A[i] >= max && A[i] < A[index]){ //注意找到的两个索引对应元素的值不能相等且是仅小于A[index]里第二大的元素 max = A[i]; max_index = i; } } //交换 swap(A,index, max_index); return A; } public void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }执行用时 : 4 ms, 在Previous Permutation With One Swap的Java提交中击败了100.00% 的用户 内存消耗 : 51.7 MB, 在Previous Permutation With One Swap的Java提交中击败了100.00% 的用户
