1053. Previous Permutation With One Swap¶
题目信息¶
- 题号:
1053
- 难度:
Medium
- 主题:
排列、单次交换、字典序前驱
- 原题:
- 重点:
最多交换一对下标,结果必须严格小于原数组,并在所有可行结果中取得字典序最大值;不存在时返回原数组
题目重述¶
给定正整数数组 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]
解释:数组已经按非递减顺序排列,交换任意两个不同元素都会使结果变大,因此保持原数组。