Next Permutation -- LeetCode 39

[Question]

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

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

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Subscribe to see which companies asked this question.

[Thoughts]
In C++ STL lib, there is a function "next_permutation()" which exactly matches the need.

To do it manually, think of the (lexicographically) largest permutation -- that must be a decreasing sequence. For any other permutations, we can come up with the following steps to get the next one:
1) Find the increasing sequence from right to left, use i to denote the position of first decreasing digit.
2) Find the fist number, from right to left,  that is larger than N[i].
3) Swap N[i] and N[j].
4) Reverse the sub-string from N[i+1] to the end.

Additional note: the "Next Greater Number III" -- LeetCode 556 is an alternative form of the same problem.

[Solution]
//
//-- Using STL --
//
void nextPermutation(vector<int>& nums) {
      next_permutation(nums.begin(), nums.end());

}

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

//
//-- Using STL again --
//
void nextPermutation(vector<int>& nums) {
    auto i = is_sorted_until(nums.rbegin(), nums.rend());
    if (i != nums.rend())
        swap(*i, *upper_bound(nums.rbegin(), i, *i));
    reverse(nums.rbegin(), i);
}