交换一次的先前排列

题目及示例

---

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

---

解题思路

---

题目主要考察的贪心算法
首先对数组进行由后向前的遍历
通过对比当前项与后一项的大小来进行判断
若 arr[i] > arr[i+1]
此时再次由后向前遍历
直到找到比 arr[i] 小的且离 arr[i] 最远的元素 arr[j]
同时保证 arr[j] 与 arr[j-1] 不相等
最后将 arr[i] 与 arr[j] 进行交换

---

代码展示

var prevPermOpt1 = function (arr) {
    let 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[j - 1] || arr[j] >= arr[i]) {
                j--
            }
            let temp = arr[j]
            arr[j] = arr[i]
            arr[i] = temp
            break
        }
    }
    return arr
}