previous-permutation-with-one-swap

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of positive integers <code>arr</code> (not necessarily distinct), return the lexicographically largest permutation that is smaller than <code>arr</code>, that can be made with exactly one swap. If it cannot be done, then return the same array.

Note that a swap exchanges the positions of two numbers <code>arr[i]</code> and <code>arr[j]</code>

&nbsp;
Example 1:

<pre>
Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.
</pre>

Example 2:

<pre>
Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.
</pre>

Example 3:

<pre>
Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 104</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 104</code></li>
</ul>

prevPermOpt1

Previous Permutation With One Swap

Greedy

Array

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

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

&nbsp;

示例 1：

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

示例 2：

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

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= arr.length &lt;= 104</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 104</code></li>
</ul>