题目描述

题目链接：31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

例子

例子 1

Input: nums = [1,2,3] Output: [1,3,2]

例子 2

Input: nums = [3,2,1] Output: [1,2,3]

例子 3

Input: nums = [1,1,5] Output: [1,5,1]

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解题思路

这道题的关键是怎么理解下一个排列顺序。以 [1,2,7,4,3,1] 为例：

通过观察，如果从后向前看，直到 7 之前，前一个数字都是比后一个数字大的，当我们看到 7 的时候，发现前一个 2 比其小，这个时候从 7 开始往后遍历，找到第一个比 2 大的数 3。此时将 2 和 3 调换一下，并把 3 之后数组元素逆转即可。

代码如下：

#include <vector>
#include <algorithm>

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

        while (left < right && nums[right] <= nums[left]) --right;
        std::swap(nums[right], nums[left]);
        std::reverse(nums.begin() + left + 1, nums.end());
    }
};

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

GitHub 代码同步地址： 31.NextPermutation.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions