题目内容

对于一个整数数组，将其元素按不同顺序排成的每一种结果都构成一个排列。把该数组所有可能的排列按照字典序从小到大依次排列，可以得到一个有序的排列序列。

现在给定一个排列 nums。如果它在上述序列中不是最后一个，请将它调整为序列中紧跟在它后面的那一个排列；如果它已经是最后一个排列，则将它调整为整个序列中的第一个排列，也就是所有元素按递增顺序排列的结果。

修改必须直接在 nums 上进行，不能使用超过常数级别的额外空间。

约束条件：

• 数组长度 $n$ 满足 $1 \le n \le 100$；
• 数组中每个元素满足 $0 \le nums[i] \le 100$。

输入描述

输入包含一个参数：一个整数数组 nums，表示需要调整的当前排列。

输出描述

返回一个整数数组，表示调整后得到的下一个排列。

样例1

输入

1
1

输出

1

说明

数组长度为 1，其唯一排列为 $[1]$。该排列已经是字典序最大的排列，不存在下一个更大排列，因此按题意调整为字典序最小的升序排列，结果仍为 $[1]$。

样例2

输入

5
1 3 5 4 2

输出

1 4 2 3 5

说明

当前排列 $[1,3,5,4,2]$ 中，右侧 $[5,4,2]$ 已经是降序，无法通过交换这些元素形成更大排列。因此找到从右向左第一个升序位置 $3<5$。

将 3 与右侧大于 3 的最小元素 4 交换，得到 $[1,4,5,3,2]$。此时交换位置之后的部分 $[5,3,2]$ 仍为降序，将其翻转为升序 $[2,3,5]$，最终得到 $[1,4,2,3,5]$。

样例3

输入

3
1 5 1

输出

5 1 1

说明

当前排列 $[1,5,1]$ 中，从右向左看第一个升序位置是 $1<5$。将较小的 1 与右侧大于它的最小元素 5 交换，得到 $[5,1,1]$。交换位置之后的部分为 $[1,1]$，翻转后仍为 $[1,1]$，因此最终结果为 $[5,1,1]$。