下一个排列

GitHub跳转原题关系图返回列表

从右找下降点，找最小更大后继交换，反转后缀。

OJ: leetcodecn

题目 ID: next-permutation

难度:普及+/提高

标签:技巧排列

日期: 2026-07-29 13:03

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求数组的下一个字典序排列。

思路

三步：1. 从右找到第一个下降点 i（nums[i] < nums[i+1]）；2. 从右找到第一个大于 nums[i] 的位置 j，交换；3. 反转 i+1 到末尾的后缀。

若完全降序则无下降点，直接反转整个数组。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    Solution().nextPermutation(a);
    for (int x : a)
        cout << x << ' ';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


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


def main():
    n = int(input())
    a = list(map(int, input().split()))
    Solution().nextPermutation(a)
    print(*a)


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)。

总结

下一个排列的关键是"反转为最小"：交换后 i 后面的后缀仍然是降序的，反转即可变成升序（最小），保证是下一个排列。