实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
class Solution {
public void nextPermutation(int[] nums) {
int minIndex = -1;
int maxIndex = -1;
for(int i=nums.length-2;i>=0;i--){
if(nums[i]<nums[i+1]){
minIndex = i;
break;
}
}
if(minIndex==-1) {
int p1 = 0,p2 = nums.length-1;
while(p1<p2){
int tmp = nums[p1];
nums[p1] = nums[p2];
nums[p2] = tmp;
++p1;
--p2;
}
return ;
}
for(int i=nums.length-1;i>minIndex;i--){
if(nums[i]>nums[minIndex]){
maxIndex = i;
break;
}
}
int tmp = nums[minIndex];
nums[minIndex] = nums[maxIndex];
nums[maxIndex] = tmp;
int p1 = minIndex+1;
int p2 = nums.length-1;
while(p1<p2){
tmp = nums[p1];
nums[p1] = nums[p2];
nums[p2] = tmp;
++p1;
--p2;
}
}
}
1.我们在找下一个排序的时候，一定是让高位的小数字和低位的大数字进行交换
2.我们在找下一个排列的时候，会尽可能让高位的小数字靠右，也就是尽可能让低位的数字变大。所以我们从低位往高位找，观察有没有数字可以被比他低位的数字替换。
以[1,2,5,4,1]为例。
我们从低位往高位找，发现2可以被后面的更大的数字替换，然后我们希望被替换后的数字尽可能的小，在[5,4,1]中比2大的最小的数字为4，所以将2和4替换。
替换后的数组为[1,4,5,2,1]，然后我们将替换的数字后面数字进行从小到大的排序即可，这时候我们需要借助一个技巧，就是被替换的数字后面的数字是降序的，比如上面的样例中，我们找到2为需要被替换的数字，2后面的数字5,4,1为降序，然后在进行替换后，后面的数字仍然是降序的，5,2,1。所以我们只需要将后面的数字进行翻转即可完成排序。
最后时间复杂度为O(n) 空间复杂度为O(1) 只借助了两个指针进行翻转。
