1053. 交换一次的先前排列)

题目地址(1053. 交换一次的先前排列)

https://leetcode.cn/problems/previous-permutation-with-one-swap/

题目描述

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

如果无法这么操作，就请返回原数组。

 

示例 1：

输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1


示例 2：

输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列


示例 3：

输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7


 

提示：

1 <= arr.length <= 104
1 <= arr[i] <= 104

前置知识

公司

• 暂无

思路

题目大意为：找到满足 i < j and arr[i] > arr[j] 的最大值。

也就是说要将 arr[i] 变小的情况下， 变得尽可能地大。为了满足这个条件， 需要 i 尽可能地大（尽可能的把低位变小，而不是高位），因此需要从大到小枚举第一个在右侧有较小值的 i。

找到 i 之后，就需要找 j 了。nums[j] 是右侧最大满足 nums[j] < nums[i] 的那个数。不难写出如下代码：

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        l = -1
        for i in range(len(arr)-1, -1, -1):
            if arr[i-1] > arr[i]:
                l = i - 1
                break
        if l == -1: return arr
        ans = 0
        r = -1
        for i in range(l+1, len(arr)):
            if arr[i] < arr[l] and arr[i] > ans:
                ans = arr[i]
                r = i
        if r == -1:
            return arr
        arr[l], arr[r] = arr[r], arr[l]
        return arr
        

实际上我们可以进一步优化常数时间，因为找 l 的过程我们有这样的信息：l 右侧是单调不递减的，因此最大的就是最后一个元素。

那么我们可以直接将数组最后一个当成 j 么？

不能！考虑 nums[j] 可能大于等于 nums[i]。比如这个 case [3,1,1,3]，我们预期是 [1,3,1,3] 而不是 [3,1,1,3]。

那是不是从右向左找到第一个小于 nums[j] 的就可以了？

不是！还是上面的 case就过不了。因此实际上是：

1. 从右往左第一个小于 arr[l] 的 arr[j]

2. arr[j] == arr[j-1]，那么优先选择 j - 1

关键点

• 需要 i 尽可能地大（尽可能的把低位变大，而不是高位），nums[j] 尽可能大

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        l = -1
        for i in range(len(arr)-1, -1, -1):
            if arr[i-1] > arr[i]:
                l = i - 1
                break
        if l == -1: return arr
        for i in range(len(arr)-1, l, -1):
            if arr[i] < arr[l] and arr[i] != arr[i-1]:
                r = i
                break
        if r == -1:
            return arr
        arr[l], arr[r] = arr[r], arr[l]
        return arr
        
            

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$

• 空间复杂度：$O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。