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
求一个排列的下一个排列，medium，比如对于排列（6,3,7,2,8,8,5,4,1），从后往前找完整的降序列，直到index=4，即8>2，此时交换2和尾部升序列中>2的第一个数4，得到（6,3,7,4,8,8,5,2,1），对于尾部的降序列进行reverse即得到下一个排列
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());
}
