题目链接:1053. 交换一次的先前排列
方法:贪心
解题思路
为了保证字典序最大,应该尽可能的使得左侧的元素不变,首先考虑交换数组靠右侧的两个数字。
-
那么可以从右往左遍历,找第一个逆序对;若没有则返回原数组;
-
找到逆序对\((i, i + 1)\)后,再对\(j\)从\(i + 1\) ~ \(n\)遍历,找\(arr[j] < arr[i]\)的最大值\(arr[j]\),然后交换\(arr[i]\) 和 \(arr[j]\)。
代码
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& arr) {
int n = arr.size();
for (int i = n - 2; i >= 0; i -- ) {
if (arr[i] <= arr[i + 1]) continue;
int j = i + 1;
int idx = j ++ ;
while (j < n) {
if (arr[j] < arr[i] && arr[j] > arr[idx]) {
idx = j;
}
j ++ ;
}
swap(arr[i], arr[idx]);
break;
}
return arr;
}
};
复杂度分析
时间复杂度:\(O(n)\);
空间复杂度:\(O(1)\)。