整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
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
思路：
参考 LeetCode题解 及注释，包含详细图解
例如 2, 6, 3, 5, 4, 1 这个排列， 我们想要找到下一个刚好比他大的排列，于是可以从后往前看。 我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，同理 5, 4, 1也不可以 直到3, 5, 4, 1这个排列，因为 3 < 5，我们可以通过重新排列这一段数字，来得到下一个排列。因为我们需要使得新的排列尽量小，所以我们从后往前找第一个比3更大的数字，发现是4。然后我们调换3和4的位置，得到4, 5, 3, 1这个数列。因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，于是我们只需要把它反转即可。最终，我们得到了4, 1, 3, 5这个数列 完整的数列则是2, 6, 4, 1, 3, 5。
这里应该针对 nums数组可能出现的情况分开讨论：
- 第一种 从左至右不包含递增序列的数组（也就是纯递减数组），例如：
[3, 2, 1]的下一个排列是[1, 2, 3]，因为 [3, 2, 1] 不存在一个字典序更大的排列。 - 第二种 从左至右包含递增序列的数组，细分的话有三种情况，但我们只关心 下一个更大的排列，这里逻辑上实则可以合并无需细分处理，分别举几个示例：
- 从左至右一直递增的数组，
[1,2,3]的下一个排列是[1,3,2] - 先递增后递减的数组，
[2,3,1]的下一个排列是[3,1,2] - 先递减后递增的数组，
[3,1,2]的下一个排列是[3,2,1]
这里需要对以上两种可能出现的数组分情况处理：
- 第一步：从后向前 循环遍历数组，找到第一个满足条件
nums[i] < nums[j]的下标i，j。 注：当然对于第一种从左至右不包含递增序列的数组（也就是纯递减数组），是找不到题目要求的 下一个更大的排列 的。因为类似 [3,2,1] 这种本身就是字典序最大的排列，是不存在一个字典序更大的排列的。 因此这里只能在第二种 从左至右包含递增序列的数组 中找到满足条件的下标i，j了。
- 继续，若在上述第二种情况中找到了满足条件
nums[i] < nums[j]的下标i，j（也表明 此时nums[i]的值是要小于其右边的任意一个数的），那么再次从数组尾元素开始，从后向前找到比当前nums[i]大的倒数第一个数nums[k]。交换nums[i]和nums[k]的值。
- 第二步：经过上面 第一步 【找到第一个满足条件
nums[i] < nums[j]的下标i，j】后，此时的nums[j:len(nums)]这后一段子数组其实是降序的。
因为在第一步中，跳出第一个for循环之前，一直都是满足条件nums[i] > nums[j]的，也就是前一个数大于后一个数，为降序。 - 第三步：将上面降序的 后一段子数组 进行反转使其升序，即可得到 下一个排列 ~
时间复杂度：O(N)
空间复杂度：O(1)
funcnextPermutation(nums []int) { iflen(nums) <=1 { return } i, j, k :=len(nums)-2, len(nums)-1, len(nums)-1// 第一步：从后向前 循环遍历数组，试图找到第一个满足条件 nums[i] < nums[j]的下标 i，j// 如果是[3 2 1]这种纯递减数组，i会一直减到-1，就进不去下面的if判断逻辑// 注意：在跳出该for循环前 nums[i] >= nums[j]，就已经能保证nums[j:len(nums)]后半段子数组为【降序】fori>=0&&nums[i] >=nums[j] { i--j-- } // i >= 0 保证不是纯降序排列，避免越界// 再次从数组尾元素开始，从后向前找到比当前 nums[i]大的倒数第一个数 nums[k]，并交换值ifi>=0 { fornums[k] <=nums[i] &&k>j { k-- } nums[i], nums[k] =nums[k], nums[i] } // 将 “后半段【降序】的子数组” 反转使其升序，即可得到 下一个排列 ~fora, b :=j, len(nums)-1; a<b; a, b=a+1, b-1 { nums[a], nums[b] =nums[b], nums[a] } }
