算法描述：

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());

    }

};