Links

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. 1.
    从右往左第一个小于 arr[l] 的 arr[j]
  2. 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。