0031 下一个排列

中等 数组 双指针

算法思路

本题思路不难，题目要求寻找比输入数组的字典序相邻更大的一个排列。 很好想到的是，我们应当从右向左遍历数组，因为从右端修改元素顺序，才能保证字典序相邻。

在从右遍历数组时，应当记录已遍历部分的最大值 max。当遍历到新元素 new 小于此最大值时，就意味着此时可以通过改变这部分元素的顺序增大数组字典序。

为了保证字典序的相邻，应先找到比 new 大但是最接近的数字 next 并进行交换。根据上述遍历规则，可知此时右端的元素一定是递减顺序。对这部分元素进行反序操作，即得题目所需排列。

代码实现

next-permutation.c

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void reverse(int *nums, int left, int right) {
    while (left < right) {
        swap(nums + left, nums + right);
        left++, right--;
    }
}

void nextPermutation(int *nums, int numsSize) {
    int i = numsSize - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = numsSize - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums + i, nums + j);
    }
    reverse(nums, i + 1, numsSize - 1);
}

/*
作者：力扣官方题解
链接：https://leetcode.cn/problems/next-permutation/solutions/479151/xia-yi-ge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/