题目描述：整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。- 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。- 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。给你一个整数数组
nums，找出nums的下一个排列。必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
这题的难点应该在读懂题目（bushi）
“ 下一个字典序更大 ” ==>> 因为是“下一个”，所以从数组末尾开始，找到一个的第一个非倒序的序列，前面的不用管，找到这个序列并将这个序列排到更大
举个栗子：[5,3,1,4,2,0]
①[1,4,2,0]，因为[4,2,0]是倒序的（不能变得更大了），加入1之后不是倒序（相当于从后向前找到第一个“<”）（可以实现得到一个更大的字典序的队列）
②将1和[4,2,0]中的大于1的最小的数（即2）交换
③[2,4,1,0]将[4,1,0]排序（即[0,1,4]）得到了[1,4,2,0]的后一个字典序更大的序列[2,0,1,4]
④和前面的拼在一起[]5,3,2,0,1,4]
贪心策略：找到逆序对① 和交换位置②
找到逆序对: 贪心的思想在于，从右向左遍历数组，寻找第一个逆序对（即
nums[index] < nums[index + 1]）。这样做的目的是找到可以被增加的最小的“值”位置找到交换位置: 在找到逆序对后，我们在逆序对的右侧寻找第一个比
nums[index]大的元素，并交换它们。这是基于一个贪心的策略，希望尽可能小地增加排列的值，以得到下一个更大的排列
代码思路：
找到逆序对: 从右向左遍历数组，找到第一个
nums[index] < nums[index + 1]的位置index。这个位置index就是逆序对的前一个元素找到交换位置: 在
index的右侧从右向左查找，找到第一个大于nums[index]的元素nums[swapindex]，并交换它们对交换位置之后的部分进行排序: 使用
Arrays.sort(nums, index + 1, nums.length)对index之后的部分进行排序，使其成为最小的排列
class Solution {
public void nextPermutation(int[] nums) {
int index = nums.length - 2;
for (; index >= 0; index--) if (nums[index] < nums[index + 1]) break;
if (index == -1) Arrays.sort(nums);
else {
int swapindex = nums.length - 1;
for (; swapindex > index; swapindex--) if (nums[swapindex] > nums[index]) break;
int swap = nums[index];
nums[index] = nums[swapindex];
nums[swapindex] = swap;
Arrays.sort(nums, index + 1, nums.length);
}
}
}优化思路：
前面的代码时间复杂度将接近O(n log n)，这个nextPermutation方法与之前的版本相比，进行了一些优化，主要是避免了使用Arrays.sort()和Arrays.sort(nums, index + 1, nums.length)，考虑到需要进行排序的序列的都是逆序的，使用了自定义的sort方法来反转数组的部分内容，时间复杂度为O(n)
class Solution {
public void nextPermutation(int[] nums) {
int index = nums.length - 2;
for (; index >= 0; index--) if (nums[index] < nums[index + 1]) break;
if (index == -1) /*Arrays.sort(nums)*/ ;
else {
int swapindex = nums.length - 1;
for (; swapindex > index; swapindex--) if (nums[swapindex] > nums[index]) break;
int swap = nums[index];
nums[index] = nums[swapindex];
nums[swapindex] = swap;
/*Arrays.sort(nums, index + 1, nums.length)*/
}
sort(nums, index + 1);
}
//需要进行的都是逆序的，因此排序的时间复杂度可以为O(n)
public void sort(int[] nums, int left) {
int right = nums.length - 1;
while (left < right) {
int swap = nums[left];
nums[left] = nums[right];
nums[right] = swap;
left++;
right--;
}
}
}
