31. 下一个排列
难度：中等
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解法一：
“下一个排列”的定义是：给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。
算法思路：
（1）如果要找到一个比目前数字大的数，一定是把一个比较靠后位置的大数和前面的一个小数进行了交换。
（2）如果要找到一个下一个排列，那么这个小数的位置i尽可能的靠后，那么我们就需要从后往前找，找到这个尽可能小的小数下标为i后；
（3）再找个尽可能小的大数，最终为了满足条件，这个大数也要尽可能靠后，所以我们也从后往前找，找到那个刚好比小数大的大数，大数的下标为j。
（4）交换后，这个数字就会比之前的数字大，但是还不是最佳的，我们上述得到的数字，从下标i以后的数字（不包括i），一定是降序排列的，因为上述的推理，类似于冒泡排序，所以，我们只要把 [i+1,len-1]，即下标i以后的数组进行倒置，变成升序，就是最后的结果了。
算法设计：
（1）从后往前找，找到第一个升序的元素 [i,i+1]，满足nums[i]<nums[i+1]，此时[i+1,len-1]一定是降序的。
（2）从后往前找，找到第一个大于元素nums[i]的下标k，即满足nums[i]<nums[k]，nums[i]就是所说的小数， nums[j]就是所说的大数。
（3）将 nums[i] 和nums[j]进行交换
（4）再将下标为[i+1,len-1]进行倒置，即将i+1往后的元素进行倒置。
（5）如果没有找到那个小数，那么说明目前的数字是最大的，那么我们就需要返回最小数，即将整个数组倒置，即进行第(4)步。
代码：
class Solution {
public void nextPermutation(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return;
}
int i = 0;
for (i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
break;
}
}
if (i >= 0) {
int j = nums.length - 1;
while (j > i) {
if (nums[i] < nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
break;
}
j--;
}
}
for (int k = i + 1; k <= (nums.length + i) / 2; k++) {
int temp = nums[k];
nums[k] = nums[nums.length - (k - i)];
nums[nums.length - (k - i)] = temp;
}
}
}
