Previous Permutation With One SwapLeetcode Problem 1053

英文原题

Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers Ai and Aj). If it cannot be done, then return the same array.

Example 1

Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2

Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3

Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Example 4

Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

Note

1 <= A.length <= 10000
1 <= A[i] <= 10000

中文翻译

给定一个由 非0数字 组成的数组（元素可能冲突），用来表达一个十进制的数。

你 可且仅可 做一次 针对数组内 两个数字互换的操作，从而生成一个新的数。

请你返回，操作后 小于当前所表达的数的 最大的数 的数字数组。

如果操作后的所有的数 都不小于当前的数，那么返回当前的数字数组。

样例 1

Input: [3,2,1]
Output: [3,1,2]
解释：交换 2 和 1

样例 2

Input: [1,1,5]
Output: [1,1,5]
解释：交换任意两个数字 都不可能形成 比现在表达的数 还小的数

样例 3

Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
解释：交换 9 和 7

样例 4

Input: [3,1,1,3]
Output: [1,3,1,3]
解释 交换 1 和 3

假设

1 <= A.length <= 10000
1 <= A[i] <= 10000

问题签名

Java 代码

1 2 3 4 5 
class Solution {    public int[] prevPermOpt1(int[] A) {     }}

Java Script 代码

1 2 3 4 5 6 7 
/*** @param {number[]} A* @return {number[]}*/var prevPermOpt1 = function(A) { };

Python 代码

1 2 
class Solution:    def prevPermOpt1(self, A: List[int]) -> List[int]: