31-下一个排列

LeetCode 31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

method

• 我们想要最小的解，所以尽可能去动位数最小的数字
• 单调递减是没有解的，如4321，所以第一个不是单调递减的位置就存在解，如1243，第一个不是单调递减的是2，即为突破口
• 把突破口的数字换成后面比自己大的最小值，才能保证最优解
• 交换之后保证后面尽可能小，就把递减变成递增，4321变成1234就变得更小

1. 从后往前找第一个非递增的数，即nums[i] < nums[i+1]
2. 从后往前找第一个大于nums[i]的数，即nums[j] > nums[i]
3. 交换nums[i]和nums[j]
4. i+1及后面的数是递减的，反转之后变成递增，保证下一个排列大于上一个排列，并且增加的幅度最小

void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = nums.size() - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums[j], nums[i]);
    }   // i<0就是全部单调递减，4321，反过来就行
    reverse(nums.begin() + i + 1, nums.end());
}