LintCode "Previous Permutation"

class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that‘s previous permuation
     */
    vector<int> previousPermuation(vector<int> &num) {
        size_t len = num.size();
        if(len < 2) return num;
        
        // step 1: find first up-side from back
        int i = len - 1;
        while (i > 0)
        {
            if (num[i - 1] > num[i]) break;
            i--;
        }
        
        // step 2: find last num smaller than num[i-1]
        int j = i;
        while (j < len)
        {
            if (num[j] >= num[i - 1]) break;
            j++;
        }
        j--;
        
        // step 3: replace num[i-1] and num[j]
        if(i > 0)
            std::swap(num[i-1], num[j]);

        // step 4: reverse all after i
        std::reverse(num.begin() + i, num.end());
        return num;
    }
};