难度: Medium
给你一个正整数数组 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 <= 1041 <= arr[i] <= 104运行时间: 29 ms
内存: 16.7 MB
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
j = n - 1
while arr[j] >= arr[i] or arr[j] == arr[j - 1]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
break
return arr
此题解采用的是从后往前扫描的贪心算法。首先，从倒数第二个元素开始向前扫描，寻找第一个比其后一个元素大的元素，记为arr[i]。这是因为我们需要找到一个尽可能靠后的位置，使得交换后得到的排列字典序小于原排列。一旦找到这样的元素，就在其右侧找到一个比它小但尽可能大的元素，记为arr[j]。为了确保交换后的排列是小于原排列的最大排列，我们需要在i右侧找到最右边的、比arr[i]小的元素。此外，还需要确保arr[j]不等于arr[j-1]，以避免重复元素导致的问题。找到合适的i和j后，交换arr[i]和arr[j]，然后返回修改后的数组。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
for i in range(n - 2, -1, -1): # 从倒数第二个元素开始向前扫描
if arr[i] > arr[i + 1]: # 找到第一个比后一个元素大的元素
j = n - 1
while arr[j] >= arr[i] or arr[j] == arr[j - 1]: # 在其右侧找到一个比它小但尽可能大的元素，且不等于前一个元素
j -= 1
arr[i], arr[j] = arr[j], arr[i] # 交换这两个元素
break
return arr # 返回修改后的数组
从倒数第二个元素向前扫描的目的是找到最近的、可以形成字典序更小的排列的点。如果从首元素或中间部分开始扫描，可能会错过更靠后的、可以通过一次交换达到最小字典序变化的机会。从后向前扫描可以最大限度地保证交换后的数组尽可能接近原数组的字典序，同时确保是小于原数组的。
选择在其右侧寻找比它小但尽可能大的元素是为了确保交换后的数组字典序最大但仍小于原数组。找到的这个元素arr[i]表示一个下降点，我们希望通过交换这个下降点，使得整体数组的变化尽量小。选择比arr[i]小但尽可能大的arr[j]可以保证尽可能维持大的数值在前面的位置，从而使交换后的数组尽可能接近原数组的字典序。
条件`arr[j] >= arr[i]`用于确保在arr[i]右侧找到一个比arr[i]小的元素。而`arr[j] == arr[j - 1]`的检查是为了避免选择重复的元素，这样做可以确保找到的arr[j]是唯一的，并且是比arr[i]小的最大值。这种选择避免了不必要的重复值交换，确保交换是有效的且结果是所需的最大字典序。
如果不检查`arr[j]`是否等于`arr[j-1]`，则可能在有重复元素的数组中选择了不正确的交换位置。例如，如果数组中有连续的相同的数值，选择了重复元素中的任意一个进行交换可能不会改变数组的字典序。确保`arr[j]`不等于`arr[j-1]`可以避免这种无效的交换，确保选择的是无重复并且使数组达到最佳状态的元素。