31. 下一个排列

题目描述

输入整数数组 nums。把它的所有排列按字典序从小到大排成一列，nums 当前的排列在这列中的后一个，就是它的下一个排列。

例如 [1,2,3] 的下一个排列是 [1,3,2]，[2,3,1] 的下一个排列是 [3,1,2]。如果当前已经是字典序最大的排列，就改成字典序最小的排列，即升序。

在 nums 上直接修改，只能使用常数级额外空间。函数不返回值，判题检查修改后的 nums。

示例 1

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2

输入：nums = [3,2,1]
输出：[1,2,3]

解释：[3,2,1] 已是最大排列，变回升序 [1,2,3]。

示例 3

输入：nums = [1,1,5]
输出：[1,5,1]

数据范围

1 <= nums.length <= 100
0 <= nums[i] <= 100

解题思路

从右找第一个下降点 i，再从右找刚好大于 nums[i] 的 j 交换，最后反转 i 后缀。

为什么正确

找到 i 后，i 右侧是非递增序列；交换并反转后缀得到最小的可行后缀。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

交换后必须反转后缀；后缀原本是降序，直接保留会错过最小增量。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
        }
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp;
            left++;
            right--;
        }
    }
}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = (int)nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }
};

func nextPermutation(nums []int) {
	i := len(nums) - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i >= 0 {
		j := len(nums) - 1
		for nums[j] <= nums[i] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	left, right := i+1, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

var nextPermutation = function(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

载入编辑器，自己跑一遍 →

技巧专题的其他题目

查看技巧全部题目 →