31 Next Permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return;
        int i, j;
        for ( i = n-2; i >= 0; i-- ) {
            if ( nums[i] < nums[i+1] ) break;
        }
        // note the special case of [5,4,3,2,1]
        if ( i == -1 ) {
            reverse(nums.begin(), nums.end() );
            return;
        }
        // find the smallest digits that is larger than nums[i];
        for ( j = n-1; j >= i+1; j-- ) {
            if ( nums[j] > nums[i] ) break;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end() );
        return;
    }
};

Notes
思路非常清晰：
（1）从后往前寻找第一个严格递减的位记为nums[i]
（2）从后往前寻找第一个大于nums[i]的位记为nums[j]
（3）则对于下一个permutation，nums[j]应该出现在i的位置；
（4）余下的数字按升序排列。

• 特别注意一些特殊情况：
• 该permutation已经是最大，对应i为-1.
• 有重复数字的时候怎么考虑？（不变）