Nicksxs's Blog ·

Leetcode 31 Next Permutation 题解分析

💡 原文中文，约1200字，阅读约需3分钟。

📝

内容提要

这篇文章讲述了如何找到下一个字典序的排列。首先找到递减序列，然后找到比递减序列中的第一个数字大的最小数字，并将其与递减序列中的第一个数字交换位置。最后，将递减序列后面的数字按照递增顺序排列。文章还提到了两种特殊情况的处理方法。

🔎

文章指出题目介绍可能误导，但字典序就是默认的字符串排序方式：逐个字符对比，同一位相同再比下一位。例如11在12前，12在13前。对于数字序列，递增序列是最小的，递减序列是最大的。理解这一点是解题的基础，避免被题目描述带偏。

解题关键是从后往前找到递减序列，因为递减序列已经是当前部分的最大排列，调整必须发生在它之前。这类似于数学进位：个位9已最大，需向前一位加1，同时将后面变为最小。找到第一个非递减元素后，在递减序列中从后往前找比它大的最小数字交换，才能得到最接近的下一个排列。

交换后，递减序列部分仍然保持递减，但这不是下一个排列，而是下N个。因为交换后整个序列已经比原序列大，要使它成为最接近的下一个，必须让后面的数字尽可能小，即变为递增序列。由于后面原本是递减的，直接反转即可得到递增，从而得到正确结果。

文章提到两种特殊情况：一是整个序列完全递减，此时下一个排列是重新开始，即整个序列排序为递增；二是序列完全递增，此时只需交换最后两位。实际上，第二种情况可以视为第一种的变体，因为完全递增时，从后往前找不到递减序列，但交换末两位即可得到下一个排列。

❓

首先从后往前找到递减序列，然后找到比递减序列中第一个数字大的最小数字进行交换，最后将后面的数字按递增顺序排列。

字典序是字符串的默认排序方式，逐个字符对比，类似于查字典的顺序。

因为递减序列已经是最大的，调整时需要在这个序列之前进行，以找到下一个最接近的排列。

当整个序列本身就是递减时，下一个排列就是将整个序列排序为递增。

对于完全递增的序列，只需交换末两位即可得到下一个排列。

在交换后，需要将递减序列后的数字按递增顺序排列，以确保得到下一个字典序的排列。