leetcode 31. 下一个排列

https://leetcode.com/problems/next-permutation/description/

31.下一个排列

整数数组的排列是将其成员排列成序列或线性顺序。

• 例如，对于arr = [1,2,3]，arr的所有排列如下：[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,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 <= 100
• 0 <= nums[i] <= 100

---

解法关键点：
考虑一种比较复杂的情况，如[2,3,5,4,1]，它的下一个排列是[2,4,1,3,5]。这种下一个排列是怎么出现的呢，

1. 对于位置i来讲，在(i, n-1]的区间上如果存在位置j，使得最小的nums[j]满足nums[j]>nums[i]，我们应该把它冒泡出来，换到i的位置上，在这个例子中就是把4换到3的位置上，集合变成[2,4,5,3,1]。即从右侧开始找到第一个升序对，交换位置。这样，一个较大的数就“晋升”上来了
   • 寻找右侧开始的升序对时，不需要做O(n^2)的遍历，因为除了这个升序对之外其他都是降序的，所以我们可以做到O(2n)的时间复杂度，第一步只要找到比nums[i+1]小的数字nums[i]，nums[i]就是升序对的左侧值，再重新从数组nums右侧开始遍历，找到第一个比nums[i]大的nums[j]就可以了，j不一定等于i+1
2. 接着我们只要把剩余的部分[i+1, n-1]做升序排序就可以了，这里面有一个优化可以避免直接O(log n)排序。当我们找到了位置j之后，有nums[i]<nums[j]，对于j来讲有nums[i+1]>...>nums[j]...>nums[n-1]，所以经过第1步的交换后的序列在[i+1, n-1]的区间上仍然是降序的，而我们只要用双指针从左右向中间夹，左右指针数值交换，就能把降序转升序了
   • 对于[i+1, j-1]区间的x来讲，一定nums[i]>nums[x]，不然第一步找出来的位置就不是j了，
   • 对于[j+1, n-1]区间的y来讲，一定nums[i]>nums[y]，不然第一步找出来的位置就不是j了，

class Solution {
    public void nextPermutation(int[] nums) {
        int idx = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                idx = i;
                break;
            }
        }
        if (idx != -1) {
            for (int i = nums.length - 1; i > idx; i--) {
                if (nums[i] > nums[idx]) {
                    int tmp = nums[idx];
                    nums[idx] = nums[i];
                    nums[i] = tmp;
                    break;
                }
            }
        }
        for (int start = idx + 1, end = nums.length - 1; start < end; start++, end--) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }
    }
}