Leetcode 31： next permutation

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

本题是要求找给定顺序的字符串的下一个permutation。暂时还不知道这题考的算法是属于哪一类，看网上的解答，发现都将这个题目当做是数学题，直接给出算法，没有分析为什么这么做是对的。 ？？？？？ 

这个题目的解题算法是： 
1. 从右往左找到第一个违背升序排列的元素index， s[i-1] < s[i]
2. 从右往左找到第一个比step1里面那个index对应的元素大的值的index
3. swap这两个元素，然后将step1里那个index后面的元素进行reverse。
4. step1里如果找不到这两个元素，那么说明整个permutation是最大的，直接reverse整个顺序就可以了。

需要扫描两遍字符组合，时间复杂度是O（2*n）
class Solution {
public:
//step1: from right to left, find the first number that violate the increasing order of elements: partitionNUmber
//step2: from right to left, find the first number that larger than the partitionNumber, this is ChangeNumber
//step3: swap these two number , and reverse all the element that is in the right of PartitionNumber
    void nextPermutation(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return;
        int partitionIdex = 0;
        int ChangeNum = 0;
        int i = 0;
        for (i = nums.size()-1; i >= 1; i--) {
            if (nums[i] > nums[i-1]) {
                partitionIdex = i-1;
                break;
            }
        }
        if (i == 0) { //the biggest nums permutation
            reverse(nums.begin(), nums.end());
            return;
        }
        for (i = nums.size()-1; i >= 0; i--) {
            if (nums[i] > nums[partitionIdex]) {
                ChangeNum = i;
                break;
            }
        }
        swap(nums[i], nums[partitionIdex]);
        reverse(nums.begin()+ partitionIdex+1, nums.end());
        return;
    }
};