Leetcpde 31.下一个排序

题目描述

整数数组的一个排列，就是将其所有成员以序列或线性顺序排列。

给定一个整数数组 $nums$，请找出 $nums$ 的下一个排列。

下一个排列是指其整数的下一个字典序更大的排列。

如果数组的所有排列按照字典序从小到大排列在一个容器中，那么数组的下一个排列就是在这个容器中排在它后面的那个排列。

如果不存在下一个更大的排列，则将这个数组重新排列成字典序最小的排列，即按升序排列。

要求必须原地修改，只允许使用常数额外空间。

输入描述

第一行输入一个整数 $n$，表示数组 $nums$ 的长度。

第二行输入 $n$ 个整数，表示数组 $nums$ 中的元素。

输出描述

输出 $n$ 个整数，表示 $nums$ 的下一个排列。

相邻两个整数之间用一个空格隔开。

样例 $1$

输入

3
1 2 3

输出

1 3 2

样例 $2$

输入

3
3 2 1

输出

1 2 3

样例解释

数组 $[3, 2, 1]$ 不存在下一个字典序更大的排列，因此将其重新排列为字典序最小的排列 $[1, 2, 3]$。

样例 $3$

输入

3
1 1 5

输出

1 5 1

数据范围

$1 <= n <= 100$

$0 <= nums[i] <= 100$