下一个排列

题目要求

给定一个整数数组nums，要求找到按照字典序排列的该数组的下一个排列。如果当前排列已经是最大的，即不存在更大的排列，则需要将数组重排为最小的排列，即其元素按照升序排列。在找到下一个排列的过程中，必须在原数组上进行修改，且只能使用常数级别的额外空间。

解题思路

解决这个问题的关键是要理解字典序排列的规则。字典序的下一个排列是比当前排列大的最小的排列。为了找到这样的排列，我们可以从后向前查找，遵循以下步骤：

从后向前查找第一个相邻升序对：从数组的末尾开始向前查找，找到第一对相邻的元素nums[i]和nums[i+1]，满足nums[i] < nums[i+1]。这一步是为了找到需要进行交换的较小数。如果找不到这样的对，说明当前排列已经是最大的排列，直接跳到步骤 4。
从后向前查找第一个大于nums[i]的元素：再次从数组的末尾开始向前查找，找到第一个大于nums[i]的元素nums[j]。
交换nums[i]与nums[j]：交换这两个元素的位置。由于nums[j]是从数组末尾向前查找时第一个大于nums[i]的元素，交换后可以保证这是比原排列大的最小排列的前缀。
翻转nums[i+1]之后的所有元素：由于nums[i+1]到数组末尾的元素是降序排列的，我们需要将它们翻转成升序排列，这样可以得到这个前缀后面的最小排列。

按照以上步骤，我们可以得到原数组的下一个排列。如果在步骤 1 中没有找到相邻的升序对，说明当前排列是最大的排列，此时直接将整个数组翻转，得到最小的排列，即完成了重排。

Golang 版本

func nextPermutation(nums []int) {
    if len(nums) <= 1 {
        return
    }

    // Step 1: 从后向前查找第一个相邻升序对(i, i+1)
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    // 如果找到了升序对，执行Step 2和Step 3
    if i >= 0 {
        // Step 2: 从后向前查找第一个大于nums[i]的元素
        j := len(nums) - 1
        for j >= 0 && nums[j] <= nums[i] {
            j--
        }
        // Step 3: 交换nums[i]和nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    }
    // Step 4: 翻转i之后的所有元素
    reverse(nums, i+1, len(nums)-1)
}

// reverse用于翻转nums数组从start到end的部分
func reverse(nums []int, start int, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

这段代码实现了上述解题思路，通过原地修改数组nums来得到其字典序的下一个排列。如果数组已经是按照降序排列的，即不存在下一个更大的排列，那么这段代码将数组修改为升序排列，即字典序最小的排列。

C++版本

#include <vector>
#include <algorithm>

void nextPermutation(std::vector<int>& nums) {
    int n = nums.size(), i, j;

    // Step 1: 从后向前查找第一个相邻升序对(i, i+1)
    for (i = n - 2; i >= 0 && nums[i] >= nums[i + 1]; --i);

    // 如果找到了升序对，执行Step 2和Step 3
    if (i >= 0) {
        // Step 2: 从后向前查找第一个大于nums[i]的元素
        for (j = n - 1; j >= 0 && nums[j] <= nums[i]; --j);
        // Step 3: 交换nums[i]和nums[j]
        std::swap(nums[i], nums[j]);
    }
    // Step 4: 翻转i之后的所有元素
    std::reverse(nums.begin() + i + 1, nums.end());
}

这段 C++代码实现了寻找数组的下一个排列的功能。它首先从后向前寻找第一个相邻的升序对，然后在这个位置之后寻找一个比当前元素大的元素进行交换，并将交换后的后面部分翻转，以确保得到的新排列是比原排列大的最小排列。如果整个数组都是降序的，那么直接翻转整个数组，得到最小的排列。

Python 版本

from typing import List

def next_permutation(nums: List[int]) -> None:
    def reverse(nums: List[int], start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1

    # Step 1: 从后向前查找第一个相邻升序对(i, i+1)
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    # 如果找到了升序对，执行Step 2和Step 3
    if i >= 0:
        # Step 2: 从后向前查找第一个大于nums[i]的元素
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # Step 3: 交换nums[i]和nums[j]
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: 翻转i之后的所有元素
    reverse(nums, i + 1, len(nums) - 1)

这段 Python 代码实现了寻找给定整数数组的下一个排列的功能。它首先从后向前寻找第一个相邻的升序对，然后在这个位置之后寻找一个比当前元素大的元素进行交换，并将交换后的后面部分翻转，以确保得到的新排列是比原排列大的最小排列。如果整个数组都是降序的，那么直接翻转整个数组，得到最小的排列。

Java 版本

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        int i = nums.length - 2;
        // Step 1: 从后向前查找第一个相邻升序对(i, i+1)
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找到了升序对，执行Step 2和Step 3
        if (i >= 0) {
            int j = nums.length - 1;
            // Step 2: 从后向前查找第一个大于nums[i]的元素
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: 交换nums[i]和nums[j]
            swap(nums, i, j);
        }

        // Step 4: 翻转i之后的所有元素
        reverse(nums, i + 1, nums.length - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }
}

这段 Java 代码实现了寻找给定整数数组的下一个排列的功能。它首先从后向前寻找第一个相邻的升序对，然后在这个位置之后寻找一个比当前元素大的元素进行交换，并将交换后的后面部分翻转，以确保得到的新排列是比原排列大的最小排列。如果整个数组都是降序的，那么直接翻转整个数组，得到最小的排列。

Rust 版本

fn next_permutation(nums: &mut Vec<i32>) {
    let mut i = nums.len() as i32 - 2;

    // Step 1: 从后向前查找第一个相邻升序对(i, i+1)
    while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
        i -= 1;
    }

    // 如果找到了升序对，执行Step 2和Step 3
    if i >= 0 {
        let mut j = nums.len() as i32 - 1;
        // Step 2: 从后向前查找第一个大于nums[i]的元素
        while j >= 0 && nums[i as usize] >= nums[j as usize] {
            j -= 1;
        }
        // Step 3: 交换nums[i]和nums[j]
        nums.swap(i as usize, j as usize);
    }

    // Step 4: 翻转i之后的所有元素
    nums[(i + 1) as usize..].reverse();
}

fn main() {
    let mut nums = vec![1, 2, 3];
    next_permutation(&mut nums);
    println!("{:?}", nums);
}

这段 Rust 代码实现了寻找给定整数向量的下一个排列的功能。它首先从后向前寻找第一个相邻的升序对，然后在这个位置之后寻找一个比当前元素大的元素进行交换，并将交换后的后面部分翻转，以确保得到的新排列是比原排列大的最小排列。如果整个向量都是降序的，那么直接翻转整个向量，得到最小的排列。

怎么样

上述解法遵循以下步骤来找到给定整数数组的下一个排列：

寻找升序对：从数组的末尾开始向前查找，找到第一个满足nums[i] < nums[i + 1]的索引i，这意味着nums[i]右边的元素都是按降序排列的。如果没有找到这样的i（即整个数组是降序的），则跳到步骤 4。
寻找交换元素：再次从数组的末尾开始向前查找，找到第一个大于nums[i]的元素nums[j]。
交换元素：交换nums[i]和nums[j]。
翻转后缀：将索引i之后的元素翻转，如果步骤 1 中没有找到升序对，这意味着整个数组都需要翻转。

这个算法保证了找到的下一个排列是大于当前排列的最小排列。如果当前排列已经是最大的，那么这个算法会将数组重排为最小的排列，即其元素按照升序排列。这个过程只需要对原数组进行修改，不需要使用额外的空间，因此它的空间复杂度是常数级别的。

hot-100