# LeetCode 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**](http://en.wikipedia.org/wiki/In-place_algorithm) and use only constant extra memory.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Example 4:**

```
Input: nums = [1]
Output: [1]
```

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

## Solution

[English Version in Youtube](https://youtu.be/0_eyN3VnTxc)

[中文版解答Youtube Link](https://youtu.be/JBX8rktJr3Y)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1DV411v7MM/)

```
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.empty()) {
            return;
        }
        
        int violation_index = num.size() - 2;
        for (; violation_index >= 0; violation_index--) {
            if (num[violation_index] < num[violation_index+1]) {
                break;
            }
        }
        
        reverse(begin(num) + violation_index + 1, end(num));
        
        if (violation_index == -1) {
            return;
        }
        
        auto it = upper_bound(begin(num) + violation_index + 1, num.end(), num[violation_index]);

        swap(num[violation_index], *it);
    }
    
};
```
