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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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

最后更新于