下一个排列

题目描述：实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

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

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

链接：https://leetcode-cn.com/problems/next-permutation/   

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：遍历数组

首先，如果数组为空或者数组只有一个元素，直接返回；

声明一个变量handled表示是否找到更大的排列，默认是false，left和right分别记录找到更大排列需要调换的数字，然后双重循环遍历数组判断是否存在更大的排列，具体遍历过程如下：

• 从数组的最后一位开始遍历，如果存在前面的数字比当前数字大的，则left和right分别记录当前索引位，并将handled更新为true，然后遍历下一位；

• 遍历过程中需要判断如果找到一种符合条件的数字，要判断是否比之前已得到的情况更优，如果是，更新left和right。

然后根据handled判断，如果为false，说明没有更大的排列，也就是不存在下一个更大排列，将数字重新排列成最小的排列，就是将顺序倒排；如果为true，则需要进行如下处理：

• 首先，将left和right位置的数字调换位置；

• 然后将 right+1 后面的数字倒排，这一步是为了将后面的数字排列成最小的值；

• 然后将 left+1到right-1 之间的数字跟 right+1到nums.length-1 的数字整体调换顺序，这一步也是为了将left后面的数字排列成最小的值；

• 然后将 left+1 位置的数字移到小于它的数字之后，这一步是为了获取最终的排列结果。

【每日寄语】 努力是人生应有的态度，睁开眼就是新的开始。