LeetCode 31. 下一个排列

Categories:

Tags:

题目描述
思路分析
1. 解法一：字典序三步法（推荐）
相似题目

题目描述

✅ 31. 下一个排列

思路分析

解法一：字典序三步法（推荐）

核心思路：

下一个排列 = 比当前排列大且最接近的排列。关键在于：尽量在靠右的位置做最小幅度的调整。

三步算法：

第一步：从右往左找”下降点” i，即第一个满足 nums[i] < nums[i+1] 的位置。若找不到（整个数组降序），说明当前是最大排列，直接翻转整个数组得到最小排列。

第二步：从右往左找第一个大于 nums[i] 的元素 nums[j]，交换 nums[i] 与 nums[j]。这使第 i 位变大了一点点（使用最接近的更大值）。

第三步：将 i+1 到末尾的部分翻转（由降序变升序）。交换后 i+1 到末尾仍是降序（最大），翻转使其变为最小，确保整体最接近。

举例：[1, 3, 5, 4, 2]

找下降点：i=1（nums[1]=3 < nums[2]=5）

找比 3 大的最右元素：j=3（nums[3]=4），交换 → [1, 4, 5, 3, 2]

翻转 i+1=2 后缀 → [1, 4, 2, 3, 5]

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，三次线性扫描

空间复杂度：O(1)，原地操作，不需要额外空间

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        // 第一步：从右往左找第一个下降点，即 nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            // 第二步：从右往左找第一个大于 nums[i] 的元素
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 交换 nums[i] 和 nums[j]，使第 i 位稍微增大
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        // 第三步：翻转 i+1 到末尾，使后缀变为最小升序
        for (int l = i + 1, r = n - 1; l < r; l++, r--) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
    }
}

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2

	// 第一步：从右往左找第一个下降点，即 nums[i] < nums[i+1]
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	if i >= 0 {
		j := n - 1
		// 第二步：从右往左找第一个大于 nums[i] 的元素
		for j >= 0 && nums[j] <= nums[i] {
			j--
		}
		// 交换 nums[i] 和 nums[j]，使第 i 位稍微增大
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 第三步：翻转 i+1 到末尾，使后缀变为最小升序
	for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
		nums[l], nums[r] = nums[r], nums[l]
	}
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯、排列生成
47. 全排列 II	中等	有重复元素的全排列
60. 排列序列	困难	字典序第 k 个排列
556. 下一个更大元素 III	中等	同思路应用于数字
1850. 邻位交换的最小次数	中等	结合下一个排列
2231. 按奇偶性交换后的最大数字	简单	排列变换

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/86157839