Leetcode.1053 交换一次的先前排列

题目链接

Leetcode.1053 交换一次的先前排列 Rating ： 1633

题目描述

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i]和 arr[j]的位置）后得到的、按字典序排列小于 arr的最大排列。

如果无法这么操作，就请返回原数组。

示例 1：

输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1

示例 2：

输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列

示例 3：

输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7

提示：

• 1<=arr.length<=1041 <= arr.length <= 10^41<=arr.length<=104
• 1<=arr[i]<=1041 <= arr[i] <= 10^41<=arr[i]<=104

解法：贪心

为了让交换后的 arr′arr'arr′ 的字典序 小于 交换之前的$arr$。我们只需要交换这样的两个数 $arr[i],arr[j]$，其中 $arr[i]>arr[j]\&\&i<j$。

并且，为了让交换之后的 arr′arr'arr′ 的字典序尽可能的大，我们要尽量选择靠右的位置的数进行交换。

所以我们最开始 从右向左遍历，找到第一个 $arr[i]>arr[i+1]$ 的数，即 $arr[i]$。（如果不存在这样的数，说明原数组 $arr$ 已经是最小字典序了，我们无法交换，直接返回 $arr$ 即可）。

接着我们再 从右往左 找到第一个 $arr[i]>arr[j]\&\&i>j$ 的数，即 $arr[j]$。（如果有多个相同的数都为$arr[j]$，那么我们应该选择最靠左边的那个，因为我们要使交换后的 arr′arr'arr′ 的字典序尽可能的大）。

最后交换这两个数 $arr[i],arr[j]$ ，返回即可。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:vector<int> prevPermOpt1(vector<int>& arr) {int n = arr.size();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[i-1] > arr[j] && arr[j] != arr[j-1]){swap(arr[i-1] , arr[j]);return arr;}}}}return arr;}
};