1053. 交换一次的先前排列

转载请声明地址四元君

1053. 交换一次的先前排列

题目难度 Medium

给你一个正整数的数组 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

思路

这个题大写的黑人问号？？？

用例最后一个给的也不对吧，怎么着1313也比1133大。想了很久结果解决超简单，就从后面往前找到非递减的换掉就好了。注意前后两个有可能一样，要找比目标换掉数字小的。

代码

class Solution { public: vector<int> prevPermOpt1(vector<int>& A) { int n=A.size(); if(n<=1) return A; bool flag=0; for(int i=n-1;i>0;i--){ if(A[i]<A[i-1]){ flag=1; for(int j=n-1;j>i-1;j--){ if(A[j]<A[i-1]){ int i=A[i-1]; A[i-1]=A[j]; A[j]=i; break; } } break; } } return A; } };