Previous Permuation

    Find the previous permutation in ascending order.

    Example

    For , the previous permutation is [1,2,3,3]

    Note

    The list may contains duplicate integers.

    题解

    和前一题 Next Permutation 非常类似，这里找上一个排列，仍然使用字典序算法，大致步骤如下：

    1. 从后往前寻找索引满足 , 如果此条件不满足，则说明已遍历到最后一个。
    2. 从后往前遍历，找到第一个比a[k]小的数a[l], 即a[k] > a[l].
    3. 交换与a[l].

    Python

    Java

    和 Permutation 一小节类似，这里只需要注意在step 1中i == -1时需要反转之以获得最大的序列。对于有重复元素，只要在 step1和 step2中判断元素大小时不取等号即可。

    复杂度分析

    最坏情况下，遍历两次原数组，反转一次数组，时间复杂度为 O(n), 使用了 temp 临时变量，空间复杂度可认为是 O(1).