数组与哈希中等1 种解法

#31下一个排列

原地把数组改为字典序中的下一个排列；若已是最大排列则改为最小排列。

#数组#双指针#排列

解题主线

从右向左找到首个 nums[pivot] < nums[pivot + 1]，其右侧必为非递增后缀。

用后缀中最右侧且大于 pivot 的值交换，再反转后缀即可得到最小增量。

解法 1：枢轴交换 + 后缀反转

定位可增大的最右位置，以后缀中的最小更大值替换，再把后缀恢复为升序。

时间复杂度

O(n)

空间复杂度

O(1)

31. 下一个排列 · 枢轴交换 + 后缀反转

java

final class Solution {
    public void nextPermutation(int[] nums) {
        int pivot = nums.length - 2;
        while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) pivot--;
        if (pivot >= 0) {
            int successor = nums.length - 1;
            while (nums[successor] <= nums[pivot]) successor--;
            swap(nums, pivot, successor);
        }
        reverse(nums, pivot + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) swap(nums, left++, right--);
    }

    private void swap(int[] nums, int left, int right) {
        int temporary = nums[left];
        nums[left] = nums[right];
        nums[right] = temporary;
    }
}

定位可增大的最右位置，以后缀中的最小更大值替换，再把后缀恢复为升序。

边界与易错点

全数组非递增时 pivot 为 -1，应直接反转整个数组。
交换对象必须是后缀中最右侧的大于 pivot 的元素。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q031_nextPermutation.java