实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
示例 4：
输入：nums = [1] 输出：[1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
思路1：
-
首先从后向前找到`pre<cur`的位置`prePos`；（即：在从后向前的升序中查找第一个破坏升序的元素位置）1.1 若`prePos`值未改变，则整个数组反转，return
-
再次在`(pre, 数组长度-1]`从后向前查找`t>pre`的位置`tPos`；（即：在从后向前的升序中查找略大于pre的元素位置）
-
`prePos`位置和`tPos`位置的元素进行交换
-
此时`(pre, 数组长度-1]`内的元素是降序，需进行反转，达到略大于原来值注意：在1中查找时可能数组是1234，需整个反转
refer: https://leetcode-cn.com/problems/next-permutation/solution/31-xia-yi-ge-pai-lie-by-qquser-2-jdbj/
具体代码：
class Solution { public void nextPermutation(int[] nums) { int n = nums.length; int idx1 = -1; for (int i=n-1; i>0; i--) { if (nums[i] > nums[i-1]) { idx1 = i - 1; break ; } } if (idx1 == -1) { reverse(nums, 0, n - 1); return ; } int idx2 = -1; for (int i=n-1; i>idx1; i--) { if (nums[i] > nums[idx1]) { idx2 = i; break ; } } swap(nums, idx1, idx2); reverse(nums, idx1 + 1, n - 1); } public void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public void reverse(int[] nums, int i, int j) { while (i < j) { swap(nums, i, j); i++; j--; } } }