1053. Previous Permutation With One Swap

题目信息

题号:

1053

难度:

Medium

主题:

排列、单次交换、字典序前驱

原题:

LeetCode 1053

重点:

最多交换一对下标,结果必须严格小于原数组,并在所有可行结果中取得字典序最大值;不存在时返回原数组

题目重述

给定正整数数组 arr。可以选择两个不同下标并交换对应元素,且整个过程最多执行一次交换。

在所有通过一次交换能够得到、并且字典序严格小于原数组的排列中,返回字典序最大的那个。若不存在任何满足条件的交换,则返回原数组不变。数组可以包含重复值,交换相等元素不产生更小排列。

1 <= arr.length <= 10^4,1 <= arr[i] <= 10^4。

自建示例

应在最靠前的位置做最小幅度下降:

输入:arr = [3,1,1,2]
输出:[2,1,1,3]
解释:交换首元素 3 与末尾的 2 可得到严格更小的排列;其他使首元素下降的交换会得到更小的字典序结果。

不存在更小的单次交换结果:

输入:arr = [1,2,3]
输出:[1,2,3]
解释:数组已经按非递减顺序排列,交换任意两个不同元素都会使结果变大,因此保持原数组。