Previous Permutation

Question

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Thoughts

与next permutation类似，将关系调整一下

Solution

class Solution:
    # @param num :  a list of integer
    # @return : a list of integer
    def previousPermuation(self, num):
        # write your code here
        if not num:
            return None
        length = len(num)
        i = length - 2
        while i >= 0:
            if num[i] > num[i+1]:
                break
            i -= 1
        #already smallest
        if i == -1:
            num.reverse()
            return num
        for j in range(i+1, length):
            if j == length - 1:
                break
            if num[j] < num[i] and num[i] <= num[j+1]:
                break
        tmp = num[i]
        num[i] = num[j]
        num[j] = tmp
        num[i+1:length] = num[length-1:i:-1]

        return num