正经题解｜上一个排列

题目解析

给定的 $origin$ 数组本质上就是规定了一个排列的顺序，我们使用一个 std::map 离散化处理下后，按照常规的 $n$ 的排列处理即可。

接下来我们看如何获取一个排列的上一个排列。

算法分析

$\bf{上一个排列}$ 的定义是：给定数字序列的字典序中上一个更小的排列。如果不存在上一个更小的排列，则将数字重新排列成最大的排列（即降序排列）。

以 $3$ 的排列为例：

123
132
213
231
312
321

那么如果获取一个排列的上一个排列呢？

我们希望上一个排列比当前排列小，这样才满足 “上一个排列” 的定义。

因此只需要将排列后面的 $\bf{「小数」}$ 与前面的 $\bf{「大数」}$ 交换，就能得到一个更小的排列。比如 $123465$，将 $5$ 和 $6$ 交换就能得到一个更小的排列 $123456$。

我们还希望上一个排列变小的幅度尽可能地小，这样才满足“上一个排列与当前排列紧邻”的要求。

为了满足这个要求，我们需要：

1. 在 $\bf{尽可能靠右的低位}$ 进行交换，需要 $\bf{从后向前}$ 查找。

2. 将一个 $\bf{尽可能大的「小数」}$ 与 $\bf{前面的「大数」}$ 交换。比如 $123645$，上一个排列应该把 $5$ 和 $6$ 交换而不是把 $4$ 和 $6$ 交换。

3. 将 $\bf{「小数」}$ 换到前面后，需要将 $\bf{「小数」}$ 后面的所有数 $\bf{重置为降序}$，降序排列就是最大的排列。
   以 $123645$ 为例：首先按照上一步，交换 $5$ 和 $6$，得到 $123\color{red}5\color{black}4\color{blue}6$；然后需要将 $5$ 之后的数重置为 $\bf{降序}$，得到 $1235\color{red}64$。显然 $1235\color{red}64$ 比 $1235\color{red}46$ 更大，$123564$ 就是 $123645$ 的上一个排列。

算法流程

1. 从后向前查找 $\bf{第一个相邻降序}$ 的元素对 $(i,j)$，满足 $P_i > P_j$。此时 $[j, end)$ 必然是升序。
2. 在 $[j,end)$ 从后向前查找第一个满足 $p_i > p_k$ 的 $k$。$p_i$、$p_k$ 分别就是上文所说的 $\bf{「大数」}$、$\bf{「小数」}$。
3. 将 $p_i$ 与 $p_k$ 交换。
4. 这时 $[j,end)$ 必然是升序（参考步骤 $1$），反转 $[j, end)$，使其降序。
5. 如果在步骤 $1$ 找不到符合要求的相邻元素对，说明当前 $[begin,end)$ 为一个升序排列，则直接跳到步骤 $4$。

AC代码

#include <bits/stdc++.h>
using namespace std;

void prev_permutation(vector<int> &p) {
    int n = p.size();
    int i = n - 1;
    while (i > 0 and p[i - 1] <= p[i]) --i;
    if (i > 0) {
        int j = n - 1;
        while (j >= i and p[j] >= p[i - 1]) --j;
        swap(p[i - 1], p[j]);
    }
    reverse(begin(p) + i, end(p));
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<int> ori(n), cur(n);
    map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        cin >> ori[i];
        mp[ori[i]] = i;
    }
    vector<int> id(n);
    for (int i = 0; i < n; ++i) {
        cin >> cur[i];
        id[i] = mp[cur[i]];
    }
    prev_permutation(id);
    for (int i = 0; i < n; ++i)
        cout << ori[id[i]] << " \n"[i + 1 == n];
    return 0;
}

复杂度分析

std::map 做离散化的时间复杂度为 $O(n\log{n})$；
获取上一个排列的时间复杂度为 $O(n)$。