本文共 1411 字，大约阅读时间需要 4 分钟。

题目描述：给定一个整数数组来表示排列，找出其上一个排列。

样例：给出排列[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

转载地址：http://vvfrf.baihongyu.com/