双倒序遍历、贪心算法：求解《31. 下一个排列》

寻找下一个较大排列的贪心策略

• 找最右的较小数：左边 < 右边 的数
• 找最右的 > 较小数 的 较大数
• 交换，较大数右侧，降序 -> 升序

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如，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 的下一个排列。 必须 原地 修改，只允许使用额外常数空间。

答案

贪心算法 · 两次倒序遍历 · 双指针交换

var nextPermutation = function(nums) {
  const n = nums.length, swap = (i, j) => {
    const t = nums[i]
    nums[i] = nums[j]
    nums[j] = t
  }
  let i = n - 1, j = n
  while(i--) if (nums[i] < nums[i + 1]) break
  if (i > -1) {
    while(j--) if (nums[j] > nums[i]) break
    swap(i, j)
  }
  l = i + 1, r = n - 1
  while (l < r) {
    swap(l, r)
    l++
    r--
  }
};

func nextPermutation(nums []int)  {
  n := len(nums)
  i := -1
  for k := n - 2; k >= 0; k-- {
    if nums[k] < nums[k + 1] {
      i = k
      break
    }
  }
  if i >= 0 {
    for j := n - 1; j >= 0; j-- {
      if nums[j] > nums[i] {
        swap(nums, i, j)
        break
      }
    }
  }
  l, r := i + 1, n - 1
  for l < r {
    swap(nums, l, r)
    l++
    r--
  }
}
func swap(nums []int, i int, j int) {
  t := nums[i]
  nums[i] = nums[j]
  nums[j] = t
}

class Solution {
    function nextPermutation(&$nums) {
      $n = count($nums);
      $i = $n - 1;
      while ($i--) if ($nums[$i] < $nums[$i + 1]) break;
      if ($i > -1) {
        for ($j = $n; $j--;) if ($nums[$j] > $nums[$i]) break;
        $this->swap($nums, $i, $j);
      }
      $l = $i + 1;
      $r = $n - 1;
      while ($l < $r) {
        $this->swap($nums, $l, $r);
        $l++;
        $r--;
      }
    }
    function swap(&$nums, $i, $j) {
      $t = $nums[$i];
      $nums[$i] = $nums[$j];
      $nums[$j] = $t;
    }
}