1053-PreviousPermutationWithOneSwap.md

交换一次的先前排列

给你一个正整数数组 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

思路：

1. 从后向前遍历：从数组的倒数第二个元素开始向前遍历，寻找第一个不符合非降序排列的元素。也就是说，寻找第一个 arr[i] > arr[i + 1] 的位置。
2. 寻找交换目标：在 arr[i] 之后寻找一个最大的元素，使得 arr[i] > arr[j] 且 arr[j] 是能够交换的最小元素。这需要从后向前查找，直到找到第一个比 arr[i] 小的元素。
3. 执行交换：一旦找到这样的 j，就交换 arr[i] 和 arr[j] 的位置。
4. 特殊情况处理：如果遍历完整个数组都没有找到可以交换的元素，说明数组已经是按字典序排列小于或等于任何可以通过一次交换得到的排列，直接返回原数组。

时间复杂度：O(n)，其中 n 是数组 arr 的长度。在最坏的情况下，可能需要遍历整个数组以找到交换的位置，并且在找到后可能需要再次遍历以找到最佳的交换目标。 空间复杂度：O(1)，算法只使用了常量级别的额外空间。

var prevPermOpt1 = function (arr) {
  const n = arr.length;
  for (let i = n - 2; i >= 0; i--) {
    if (arr[i] > arr[i + 1]) {
      let j = n - 1;
      while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
        j--;
      }
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      break;
    }
  }
  return arr;
};