上一個排列

題目描述：給定一個整數數組來表示排列，找出其上一個排列。

樣例：給出排列[1,3,2,3]，其上一個排列是[1,2,3,3]；給出排列[1,2,3,4]，其上一個排列是[4,3,2,1]

方法與之前的“下一個排列”問題類似（詳見：點選打開連結），如果上一個問題沒有搞明白，請先移步給出的連結。在講解這個問題之前，我會假設你已經完全明白“字典序”，“高位”，“低位”這些概念。

好了，看本題。找上一個排列，其實兩個相鄰的排列一定是滿足擁有最長字首的。是以，在“下一個排列”的問題中，我們是從右往左開始尋找需要改變的高位，這裡，依然是類似的，我們從右往左開始尋找需要改變的高位。但是，不同的是，因為求取的是上一個排列，是以，我們找尋的目的是找到一個數值高的高位，将其數值變低，這一點與“下一個排列”是相反的。

是以，可以這樣尋找：從右往左，找第一個不是降序的位置：例如，[2, 1, 3]，3到1，降序；1到2，升序。于是定位需要改變的高位為數值2所在的位置。然後再從右往左尋找第一個比這個高位數值小的數，交換。這裡，我們找到了1，于是，交換1和2，變成[1, 2, 3]；最後，與“下一個排列”同理，因為隻是上“一”個，是以，需要将高位之後的部分數組按降序排列。此處[1, 2, 3] -> [1, 3, 2]. 整個過程完成。

代碼如下：

class Solution:
    # @param num :  a list of integer
    # @return : a list of integer
    def previousPermuation(self, num):
        n = len(num)
        right = n - 1
        # 從右往左，找第一個升序
        while right > 0:
            if num[right] < num[right - 1]:
                break
            else:
                right -= 1
        # 如果整個數組是降序排列，颠倒過來
        if right == 0:
            num.reverse()
            return num
        # 定位需要交換的高位
        right -= 1
        index = n - 1
        # 從右往左，找第一個比這個高位小的低位
        while index > right:
            # 交換高地位
            if num[index] < num[right]:
                num[index], num[right] = num[right], num[index]
                break
            else:
                index -= 1
        # 将被交換的高位之後的部分數組按逆序排列，因為隻是上1個
        return num[:right + 1] + sorted(num[right + 1:], reverse=True)
        # write your code here