What is the main pattern to recognize in Previous Permutation With One Swap?

Identify a rightmost decrease where a single swap can produce a smaller permutation, following a greedy choice to select the largest smaller candidate.

How do duplicates affect swapping decisions?

You must select the rightmost largest smaller duplicate to ensure maximal lexicographic order; swapping with an earlier duplicate may yield a suboptimal result.

Can this algorithm handle arrays of length 10^4 efficiently?

Yes, the method scans the array twice linearly, achieving O(n) time and O(1) space, suitable for large arrays.

What if the array is already the smallest permutation?

No valid swap exists; the algorithm correctly returns the original array unchanged.

Why is a greedy choice plus invariant validation crucial here?

It ensures the selected swap produces the largest possible previous permutation without violating the single-swap requirement.

#1053

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

交换一次的先前排列

给你一个正整数数组 arr （可能存在重复的元素），请你返回可在一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。如果无法这么操作，就请返回原数组。示例 1：输入： arr = [3,2,1] 输出： [3,1,2] 解释： …

数组贪心

题目描述

给你一个正整数数组 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 <= 10⁴
1 <= arr[i] <= 10⁴

lightbulb

解题思路

方法一：贪心

我们先从右到左遍历数组，找到第一个满足 $arr[i - 1] \gt arr[i]$ 的下标 $i$ ，此时 $arr[i - 1]$ 就是我们要交换的数字，我们再从右到左遍历数组，找到第一个满足 $arr[j] \lt arr[i - 1]$ 且 $arr[j] \neq arr[j - 1]$ 的下标 $j$ ，此时我们交换 $arr[i - 1]$ 和 $arr[j]$ 后返回即可。

如果遍历完数组都没有找到满足条件的下标 $i$ ，说明数组已经是最小排列，直接返回原数组即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	complexity is O(n) since we scan the array twice: once to find the pivot and once to select the swap candidate. Space complexity is O(1) as we perform swaps in-place without extra structures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can you find a single swap that reduces the permutation while keeping it maximal?
question_mark
How do you efficiently locate the candidate for swapping to preserve lexicographic order?
question_mark
What invariant ensures that your swap choice produces the largest smaller permutation?

warning

常见陷阱

外企场景

error
Swapping with the first smaller element instead of the largest smaller one can produce a suboptimal result.
error
Not scanning from right to left may miss the pivot producing the largest decrease.
error
Failing to handle duplicate numbers correctly can lead to incorrect swaps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Previous permutation allowing multiple swaps instead of exactly one.
arrow_right_alt
Next permutation with one swap using a similar greedy selection but reversed criteria.
arrow_right_alt
Finding the k-th previous permutation under a single-swap constraint.

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #1029 两地调度 #1024 视频拼接