LeetCode 题解工作台
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如， arr = [1,2,3] ，以下这些都可以视作 arr 的排列： [1,2,3] 、 [1,3,2] 、 [3,1,2] 、 [2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们先从后往前遍历数组 ，找到第一个满足 $nums[i] \lt nums[i + 1]$ 的位置 ，那么 就是我们需要交换的元素，而 $nums[i + 1]$ 到 $nums[n - 1]$ 的元素是一个降序序列。 接下来，我们再从后往前遍历数组 ，找到第一个满足 $nums[j] \gt nums[i]$ 的位置 ，然后我们交换 和 。最后，我们将 $nums[i + 1]$ 到 $n…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
解题思路
方法一：两次遍历
我们先从后往前遍历数组 ，找到第一个满足 的位置 ，那么 就是我们需要交换的元素，而 到 的元素是一个降序序列。
接下来，我们再从后往前遍历数组 ，找到第一个满足 的位置 ，然后我们交换 和 。最后，我们将 到 的元素反转，即可得到下一个排列。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
if ~i:
j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 :] = nums[i + 1 :][::-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Checks for efficient in-place manipulation of the array.
- question_mark
Assesses understanding of permutations and their properties.
- question_mark
Tests ability to apply two-pointer techniques and invariant tracking in array problems.
常见陷阱
外企场景- error
Forgetting to reverse the suffix after swapping.
- error
Not correctly identifying the largest decreasing suffix.
- error
Misunderstanding the termination condition when no next permutation is possible.
进阶变体
外企场景- arrow_right_alt
Generate the previous permutation instead of the next.
- arrow_right_alt
Handle larger arrays with more elements.
- arrow_right_alt
Optimize the solution for specific types of input arrays.