原文：31. 下一个排列(力扣 面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-031/

题目：

难度：Middle

相关话题：数组

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地 修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路：

从最低位开始找(倒序遍历)；

  1. 如果当前nums[i]的后面存在一个数nums[k]>nums[i]，那么交换i和k就是当前下一个的排列。

  2. 如果不能存在这个数，那么说明nums[i]比它后面所有的数都大，要将它放到最末尾，通过插入排序的方法，将它与后面一个个交换直到末尾。

也就是说，对于nums[i]，它后面的是一个递增序列，递增序列才能保证存在条件1的数nums[k]是一个比nums[i]大的最小值。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  for(let i=nums.length-2;i>=0;i--){
    for(let k=i;k<nums.length-1;k++){
      if(nums[i]<nums[k+1])return swap(nums,i,k+1)
    }
    for(let k=i;k<nums.length-1;k++){
      swap(nums,k,k+1)
    }
  }
  function swap(arr,i,j){
    let t=arr[i]
    arr[i]=arr[j]
    arr[j]=t
  }
};