leet1053.previous-permutation-with-one-swap

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

---

思路

贪心，题目要我们找前一个排列，意思是这个排列在字典序上比当前排列小。但又是所有比当前排列小中的最大的一个。思考，

• 从后往前看，如果数值依次递减，那任意两个交换会产生逆序对。例如【4，5，6】随便换一下【4，6，5】，发现了吗，字典序变大了。所以肯定不能这么换。
• 因此要从后往前，找到第一个逆序对，记为 $(a_i,a_{i+1})$，满足 $a_i>a_{i+1}\le a_{i+2}\le \cdots \le a_n$. 贪心的策略是，$a_i$ 与 $\max \{a_j|j\in [i+1,n]\text{and}{a}_j<a_i\}$ 交换。即与其后面的元素中最大但小于 $a_i$ 的那个交换。
  • $a_i$ 前面高位的元素不要动，因为通过上述交换已经能获得一个更小的排列。如果把前面高位换的更小，得到的排列会比只换 $a_i$ 之后的元素更小。
  • 将拟要交换的元素记为 $x=\max \{a_j|j\in [i+1,n]\text{and}{a}_j<a_i\}$，随便取后面一个元素 $a_k:a_k\ne x,a_k<a_i$ 交换，得到的排列显然比和 $x$ 交换更小。
  • 注意：如果有多个元素满足 $x$ 的条件，那么要选择最左边的，这样交换之后可以让较大的数字在高位，得到的排列字典序更大。

Code

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        if (arr.size() == 1) return arr;
        int i = arr.size() - 1;
        for (; i > 0; --i) {
            if (arr[i] < arr[i - 1]) break;
        }
        if (i == 0) {
            // already a min perm
            return arr;
        }
        int max_idx_to_swap = -1;
        for (int j = arr.size() - 1, curmax = -1; j >= i; --j) {
            // 要交换的元素不能大于前面那个，否则交换之后字典序变大
            // 如果有重复元素，要一直往前贪心，保证交换后，前面较大的数字在高位，这样整体字典序更大。
            if (arr[j] >= curmax && arr[j] < arr[i-1]) {
                curmax = arr[j];
                max_idx_to_swap = j;
            }
        }
        std::swap(arr[i-1], arr[max_idx_to_swap]);
        return arr;
    }
};

see also leet31.next-permutation