交换一次的先前排列【LC1053】
给你一个正整数数组
arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字arr[i]和arr[j]的位置）后得到的、按字典序排列小于arr的最大排列。如果无法这么操作，就请返回原数组。
虽然写出来了，但是花了55分钟…
还是有思路但是思路不清晰，然后直接敲代码，改来改去，老毛病了
笔试绝对ggg
看了别人的贪心，感觉自己笨笨的
思路：贪心
假设交换的左边元素为a r r [ i ] ，右边的元素为a r r [ j ]
怎样交换一次可以使字典序减小？
交换元素a r r [ i ] > a r r [ j ] 时，可以使字典序较小，所以数组必须是非递增的
如何使字典序小于原数组的情况下最大？【贪心】
保留前面高位部分的数组，尽可能交换低位部分的数组，即尽可能最小化j jj的同时，最大化i ii
枚举每个右端点，此时的右端点r rr必须小于等于n u m s [ j ] ，找到在[ i , r − 1 ] [i,r-1][i,r−1]范围内，从右往左第一个大于其的左端点进行交换
如果a r r [ r ] > a r r [ j ] , 那么从右往左第一个大于a r r [ r ] 的左端点一定在i的左边包括i，那么我们无法获得比目前的排列更大的排列
如果a r r [ r ] = = a r r [ j ] , 那么从右往左第一个大于a r r [ r ] 的左端点还是为i ii，只需要修改右端点
如果a r r [ r ] < a r r [ j ]
实现
class Solution { public int[] prevPermOpt1(int[] arr) { int n = arr.length; int l = 0; // 升序数组本身就是最小排列 while (l < n - 1 && arr[l] <= arr[l + 1]){ l++; } if (l == n - 1) return arr; // 升序数组 // 非升序数组 枚举每个右端点 找到从右往左第一个大于其的左端点进行交换 // 之后交换的右端点必须小于等于arr[j]，并且左端点l必须大于i才能使交换结果变小 // 如果arr[r] > arr[j], 那么从右往左第一个大于arr[r]的左端点一定在i的左边包括i，那么我们无法获得比目前的排列更大的排列 // 如果arr[r] == arr[j], 那么从右往左第一个大于arr[r]的左端点还是为i，只需要修改右端点 // 如果arr[r] < arr[j], 那么l需要在[i+1,r-1]的范围内才可能是字典序增大 int i = -1, j = -1;// 记录最终的交换结果 for (int r = n - 1; r > i; r--){ if (j != -1 && arr[r] > arr[j]) continue; if (j != -1 && arr[r] == arr[j]) { j = r; continue; } for (l = r - 1; l >= (i != -1 ? i + 1 : 0); l--){ if (arr[l] > arr[r]){ i = l; j = r; break; } } } // 交换 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; return arr; } }
复杂度
时间复杂度：O ( n 2 )
空间复杂度：O ( 1 )
别人的贪心
我们先从右到左遍历数组，找到第一个满足 a r r [ i − 1 ] > 的下标 i ，此时 a r r [ i − 1 ]就是我们要交换的数字，我们再从右到左遍历数组，找到第一个满足 a r r [ j ]
=arr[j−1] 的下标 j，此时我们交换 a r r [ i − 1 ] 和 a r r [ j ] 后返回即可。
class Solution { public int[] prevPermOpt1(int[] arr) { int n = arr.length; for (int i = n - 1; i > 0; --i) { if (arr[i - 1] > arr[i]) { for (int j = n - 1; j > i - 1; --j) { if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) { int t = arr[i - 1]; arr[i - 1] = arr[j]; arr[j] = t; return arr; } } } } return arr; } } 作者：ylb 链接：https://leetcode.cn/problems/previous-permutation-with-one-swap/solutions/2205403/python3javacgotypescript-yi-ti-yi-jie-ta-pxxt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n )
空间复杂度：O ( 1 )
