LeetCode 热题 HOT 100 第15天：“下一个排列”

LeetCode 热题 HOT 100 第15天：“下一个排列”

继续刷LeetCode 热题 HOT 100 的题目，并且在博客更新我的solutions。在csdn博客中我会尽量用文字解释清楚，相关Java代码大家可以前往我的个人博客jinhuaiyu.com中查看。
题目：下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 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 <= 100
0 <= nums[i] <= 100

solution：
我们需要找到排列的规律，除了特殊情况，即这个数组已经是降序排列的了，此时下一个排列就变回了最小的数，即每个数字升序排列。其他情况下，需要找出统一的规律，首先我们可以自己写一些排列：
123456
123465
123546
123564
123645
这些排列中是按排列顺序来的，我们可以发现三个规律：
一：下一个排列和上一个排列相比，存在一个位置i，i的左边都一样。怎么找到这个i呢，我们可以观察前一个排列，从右往左观察，其实nums[i]和nums[i+1]就是第一对前者比后者小的数。比如从123465到123546，i是第四位，对于前一个排列来说，6>5，所以不是；4>6，所以i应该是数字4所在的第四位。大家可以多写一些排列数自己看看这个规律。
二：下一个排列应该是要比上一个排列的数大，但变大的幅度要尽可能小。我们想让第i位的数变大，只能在i+1到尾部这些数字里面找比第i位大的数；而为了尽可能使变大幅度小，则必须找到符合前面条件里最小的那个数字。我们可以发现，从i+1开始，数字都是呈降序的，也就是说，从最左边开始找第一个比nums[i]大的数就是要放到i位置的数，假设这个位置是j。从排列123465到123546，对于前一个排列，i是位置4，j是位置6。将这两个位置的数字交换，123465就变成了123564，到了第二步结束，我们已经很接近下一个排列了。
三：我们可以发现，不管是在交换ij之前还是之后，i+1到末尾的这些数字都是按降序排列的，而最终的下一个排列，从i+1开始，则是升序排列的。所以最后一步就是把i+1及其后面的位置的数字的排序由降序改成升序即可。12564中的64改成46，就得到了最终结果123546。这并不需要重新排序，本来就是有序的数，直接翻转过来就行了。
事实上，我们的算法也是分成上面三步来执行的，先找到i，再找到j并和i位置交换，最后把i+1及其后面的数由降序改成升序，就得到了下一个排列。
附：对于特殊情况，即数组也就是654321，成为全降序排列了，下一个排列应该是全升序排列123456。这种情况不需要找到i和j以及交换，直接进入第三步，反转排序即可，通过判断i是否能找合理的位置找到，可以和其他情况合并到一起处理。

Finally，带有详细注释的代码放在放在我的个人博客http://jinhuaiyu.com/leetcode-next-permutation/