分析

• 本题的考点：数组。

• 本题考察的是c++中next_permutation的实现。

• 思路是：寻找最后一个严格上升对的前一个元素e，然后寻找e后面大于e的最小的元素x，交换e和x，然后将最后的下降序列翻转即可，如下图：

代码

• C++

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {

        int k = nums.size() - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {  // 说明是最大值
            reverse(nums.begin(), nums.end());
        } else {
            int t = k;
            while (t < nums.size() && nums[t] > nums[k - 1]) t++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

• Java

class Solution {
    public void nextPermutation(int[] nums) {

        int k = nums.length - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {  // 说明是最大值, 返回最小值
            reverse(nums, 0, nums.length - 1);
        } else {
            int t = k;
            while (t < nums.length && nums[t] > nums[k - 1]) t++;
            swap(nums, k - 1, t - 1);
            reverse(nums, k, nums.length - 1);
        }
    }

    // 翻转nums[i...j]
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++; j--;
        }
    }

    // 交换nums[i], nums[j]
    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。

• 空间复杂度：$O(n)$，n为数组长度。