算法描述:
Find largest index i such that array[i − 1] < array[i].
Find largest index j such that j ≥ i and array[j] > array[i − 1].
Swap array[j] and array[i − 1].
Reverse the suffix starting at array[i].
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// void nextPermutation(vector<int>& nums) {
// //find the fisrt non-increacing number from the end
// if(nums.size() < 2) return;
// vector<int>::reverse_iterator it = nums.rbegin();
// while((it+1) != nums.rend() && *(it+1) >= *it) it++;
// if(it+1 == nums.rend()){
// reverse(nums.begin(), nums.end());
// }
// else{
// //find the min number greater than *(it + 1)
// vector<int>::reverse_iterator itb = it+1;
// vector<int>::reverse_iterator ite = nums.rbegin();
// while(ite != itb && *ite <= *itb) ite++;
// int temp = *ite;
// *ite = *itb;
// *itb = temp;
// reverse(nums.rbegin(), itb);
// }
// }
void nextPermutation(vector<int>& nums) {
if(nums.size() < 2) return;
int pos = nums.size();
while(--pos > 0){
if(nums[pos] > nums[pos - 1]){
int pivot = pos -1;
int back = nums.size();
while(nums[--back] <= nums[pivot]){};
swap(nums[pivot], nums[back]);
break;
}
}
reverse(nums.begin()+pos,nums.end());
}
};