LeetCode 31. 下一个排列

题目描述

✅ 31. 下一个排列

image-20230305171846186

思路分析

本题核心是字典序排列。

image-20230305192649898

image-20250510095837206

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24



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] 大的数 nums[j]
		for j >= 0 && nums[j] <= nums[i] {
			j--
		}
		// 交换 nums[i] 和 nums[j]
		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]
	}
}
  • 时间复杂度：O (n)
  • 空间复杂度：O (1)

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/86157839
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！