LC1053. 交换一次的先前排列

题目链接：LC1053. 交换一次的先前排列

题解

• 第一次碰到num list 的字典序，数字大的字典序大。

• 题目合法交换就是去找一个逆序数，即 i<j, arr[i]>arr[j]。结合字典序最大条件，就是要 i 最大，i 最大情况下，还要 j 最大。这种方法的复杂度应该是 $O(n^2)$

• 官方题解复杂度是 $O(n)$，枚举 i: n-2 -> 0，有一个隐含的假设已经枚举过的 [i,n) 是非递减的。

参考代码

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        mp = {}
        a = -1
        b = -1
        n = len(arr)
        for i in range(n-1, -1, -1):
            for j in range(i-1, -1, -1):
                if j <= a:
                    break
                if arr[j] > arr[i]:
                    a = j
                    b = i
        
        if a == -1:
            return arr
        else:
            for j in range(a, b):
                if arr[b] == arr[j]:
                    b = j
                    break
            tmp = arr[a]
            arr[a] = arr[b]
            arr[b] = tmp
        return arr