https://leetcode.com/problems/next-permutation/description/
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
符合直觉的方法是我们按顺序求出所有的排列，如果当前排列等于 nums，那么我直接取下一个 但是这种做法不符合 constant space 要求（题目要求直接修改原数组）,时间复杂度也太高，为 O(n!),肯定不是合适的解。
这种题目比较抽象，写几个例子通常会帮助理解问题的规律。我找了几个例子，其中蓝色背景表示的是当前数字找下一个更大排列的时候需要改变的元素.
我们不难发现，蓝色的数字都是从后往前第一个不递增的元素，并且我们的下一个更大的排列 只需要改变蓝色的以及之后部分即可，前面的不需要变。
那么怎么改变蓝色的以及后面部分呢？为了使增量最小， 由于前面我们观察发现，其实剩下的元素从左到右是递减的，而我们想要变成递增的，我们只需要不断交换首尾元素即可。
另外我们也可以以回溯的角度来思考这个问题，让我们先回溯一次：
这个时候可以选择的元素只有2，我们无法组成更大的排列，我们继续回溯，直到如图：
我们发现我们可以交换4或者2实现变大的效果，但是要保证变大的幅度最小（下一个更大）， 我们需要选择最小的，由于之前我们发现后面是从左到右递减的，显然就是交换最右面大于1的。
之后就是不断交换使之幅度最小：
- 写几个例子通常会帮助理解问题的规律
- 在有序数组中首尾指针不断交换位置即可实现reverse
- 找到从右边起
第一个大于nums[i]的，并将其和nums[i]进行交换
/*
* @lc app=leetcode id=31 lang=javascript
*
* [31] Next Permutation
*/
function reverseRange(A, i, j) {
while (i < j) {
const temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
}
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
// 时间复杂度O(n) 空间复杂度O(1)
if (nums == null || nums.length <= 1) return;
let i = nums.length - 2;
// 从后往前找到第一个降序的,相当于找到了我们的回溯点
while (i > -1 && nums[i + 1] <= nums[i]) i--;
// 如果找了就swap
if (i > -1) {
let j = nums.length - 1;
// 找到从右边起第一个大于nums[i]的，并将其和nums[i]进行交换
// 因为如果交换的数字比nums[i]还要小肯定不符合题意
while (nums[j] <= nums[i]) j--;
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 最后我们只需要将剩下的元素从左到右，依次填入当前最小的元素就可以保证是大于当前排列的最小值了
// [i + 1, A.length -1]的元素进行反转
reverseRange(nums, i + 1, nums.length - 1);
};