mplement 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

本題其實是考你全排列怎么生成，具體就是stl里的next_permutation() 的實現(xiàn)，類似的我們還可以問pre_permutation()怎么實現(xiàn)(就是符號換一下)，具體參考stl源碼解析。

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        if(nums.size() <= 1) return;
        vector<int>::iterator first = nums.begin();
        vector<int>::iterator last = nums.end();

        int count = nums.size() - 1;//找合適couple的最大次數(shù)

        vector<int>::iterator i = last - 2;
        vector<int>::iterator ii = last - 1;
        while(count > 0)
        {
            if ((*i) < (*ii))
            {
                break;
            }
            else
            {
                i--;
                ii--;
                count--;
            }
        }

        if (count == 0) //整個序列已經(jīng)沒有更大的了，需要返回最小的
        {
            reverse(first, last);
        }
        else
        {
            vector<int>::iterator j = last - 1;
            while( (*j) <= (*i) ) j--;

            int temp = (*j);//交換i， j
            (*j)=(*i);
            (*i)=temp;
            
            reverse(ii, last);
        }

    }
};