```
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int end = nums.size() - 1, start = end - 1;
for ( ; start >= 0 && nums[start] >= nums[start + 1]; --start) ;
if (start == -1) {
reverse(nums.begin(), nums.end());
return ;
} else {
int minidx = start + 1;
for ( ; minidx + 1 < nums.size(); ++minidx) {
if (nums[minidx + 1] <= nums[start]) break;
}
swap(nums[start], nums[minidx]);
sort(nums.begin() + (start + 1), nums.end());
return ;
}
}
};
```

Given array : [1, 3, 2, 4, 9, 8, 7, 6, 5]

- As you can find, the last five elements are in
**reverse**order [1, 3, 2, 4, | 9, 8, 7, 6, 5]. - Which means, if the given array is [9, 8, 7, 6, 5], then it is already the
**last permutation**of these five elements, we cannot "increase" it anymore. - Then we should find the
**least significant number**of the remaining array. Among the first four numbers, [1, 3, 2, 4], the least significant number is always on the**last position**of this array, and it's 4 (nums[3]). - Then this problem is reduced to find
**the next permutation of [4, | 9, 8, 7, 6, 5]**. Because we'll never need to touch the first three numbers to get the next permutation. - Because 4 (nums[3]) is on the least significant position, and [9, 8, 7, 6, 5] cannot be any larger. To get the next permutation, we need to
**"increase" nums[3] by the smallest possible step**and**"decrease" the nums[4:8] to its "smallest" permutation**. - To get the smallest "increase" on nums[3], we need to find the
**smallest element in [9, 8, 7, 6, 5] that is larger than nums[3]**. After swapping these two number, we need to decrease nums[4:8] to the smallest, a.k.a. in the sorted order.

The steps are:

[1, 3, 2, **4**, | 9, 8, 7, 6, 5]

--> [1, 3, 2, |**4**, 9, 8, 7, 6, 5]

--> [1, 3, 2, |**4**, 9, 8, 7, 6, **5**]

--> [1, 3, 2, |**5**, 9, 8, 7, 6, **4**]

--> [1, 3, 2, **5**, |9, 8, 7, 6, **4**]

--> [1, 3, 2, 5, |**4, 6, 7, 8, 9**]

Hope this post can help you :)