31. 下一个排列

• 题号：31
• 来源：LeetCode
• 难度：中等
• 标签：数组 原地算法
• 语言：TypeScript
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-27

TypeScript · O(n) 时间 · O(1) 空间 · 更新于 2026-09-27

从右找升序对，反转后缀再交换进位

/**
 * @difficulty medium
 * @tags 数组,原地算法
 * @time O(n)
 * @space O(1)
 * @note 从右找升序对，反转后缀再交换进位
 * @31. 下一个排列
 */
function nextPermutation(nums: number[]) {
    const n = nums.length;

    for (let i = n - 1; i >= 1; i--) {
        if (nums[i - 1] < nums[i]) {
            // 将 i 到末尾反转（因为原本是降序）
            reverse(nums, i, n - 1);

            // 在 i 到末尾中找到第一个大于 nums[i-1] 的数并交换
            for (let j = i; j < n; j++) {
                if (nums[j] > nums[i - 1]) {
                    [nums[j], nums[i - 1]] = [nums[i - 1], nums[j]];
                    break;
                }
            }
            return;
        }

        // 如果整个数组都是降序，直接反转
        if (i === 1) {
            reverse(nums, 0, n - 1);
        }
    }
};

// 原地反转数组的辅助函数
function reverse(arr: number[], left: number, right: number) {
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

源码：ts/leetcode/31. 下一个排列.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm