Description
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
Solution
求一個(gè)排列的下一個(gè)排列嘉蕾，medium错忱，比如對于排列（6,3,7,2,8,8,5,4,1），從后往前找完整的降序列掷倔，直到index=4勒葱，即8>2错森，此時(shí)交換2和尾部升序列中>2的第一個(gè)數(shù)4涩维，得到（6,3,7,4,8,8,5,2,1）蜗侈，對于尾部的降序列進(jìn)行reverse即得到下一個(gè)排列
void nextPermutation(vector<int>& nums) {
int topIndex = nums.size() - 1;
while (topIndex > 0 && nums[topIndex] <= nums[topIndex - 1]) {
topIndex--;
}
if (topIndex == 0) {//如果是全部降序踏幻，即最大排列该面，返回升序列
std::reverse(nums.begin(), nums.end());
return ;
}
int swapIndex = nums.size() - 1;
while (nums[swapIndex] <= nums[topIndex - 1]) {
swapIndex--;
}
swap(nums[topIndex - 1], nums[swapIndex]);
std::reverse(nums.begin() + topIndex, nums.end());
}
