题目解析
给定的 originoriginorigin 数组本质上就是规定了一个排列的顺序,我们使用一个 std::map 离散化处理下后,按照常规的 nnn 的排列处理即可。
接下来我们看如何获取一个排列的上一个排列。
算法分析
上一个排列\bf{上一个排列}上一个排列 的定义是:给定数字序列的字典序中上一个更小的排列。如果不存在上一个更小的排列,则将数字重新排列成最大的排列(即降序排列)。
以 333 的排列为例:
那么如果获取一个排列的上一个排列呢?
我们希望上一个排列比当前排列小,这样才满足 “上一个排列” 的定义。
因此只需要将排列后面的 「小数」\bf{「小数」}「小数」 与前面的 「大数」\bf{「大数」}「大数」 交换,就能得到一个更小的排列。比如 123465123465123465,将 555 和 666 交换就能得到一个更小的排列 123456123456123456。
我们还希望上一个排列变小的幅度尽可能地小,这样才满足“上一个排列与当前排列紧邻”的要求。
为了满足这个要求,我们需要:
1. 在 尽可能靠右的低位\bf{尽可能靠右的低位}尽可能靠右的低位 进行交换,需要 从后向前\bf{从后向前}从后向前 查找。
2. 将一个 尽可能大的「小数」\bf{尽可能大的「小数」}尽可能大的「小数」 与 前面的「大数」\bf{前面的「大数」}前面的「大数」 交换。比如 123645123645123645,上一个排列应该把 555 和 666 交换而不是把 444 和 666 交换。
3. 将 「小数」\bf{「小数」}「小数」 换到前面后,需要将 「小数」\bf{「小数」}「小数」 后面的所有数 重置为降序\bf{重置为降序}重置为降序,降序排列就是最大的排列。
以 123645123645123645 为例:首先按照上一步,交换 555 和 666,得到 123546123\color{red}5\color{black}4\color{blue}6123546;然后需要将 555 之后的数重置为 降序\bf{降序}降序,得到 1235641235\color{red}64123564。显然 1235641235\color{red}64123564 比 1235461235\color{red}46123546 更大,123564123564123564 就是 123645123645123645 的上一个排列。
算法流程
1. 从后向前查找 第一个相邻降序\bf{第一个相邻降序}第一个相邻降序 的元素对 (i,j)(i,j)(i,j),满足 Pi>PjP_i > P_jPi >Pj 。此时 [j,end)[j, end)[j,end) 必然是升序。
2. 在 [j,end)[j,end)[j,end) 从后向前查找第一个满足 pi>pkp_i > p_kpi >pk 的 kkk。pip_ipi 、pkp_kpk 分别就是上文所说的 「大数」\bf{「大数」}「大数」、「小数」\bf{「小数」}「小数」。
3. 将 pip_ipi 与 pkp_kpk 交换。
4. 这时 [j,end)[j,end)[j,end) 必然是升序(参考步骤 111),反转 [j,end)[j, end)[j,end),使其降序。
5. 如果在步骤 111 找不到符合要求的相邻元素对,说明当前 [begin,end)[begin,end)[begin,end) 为一个升序排列,则直接跳到步骤 444。
AC代码
复杂度分析
std::map 做离散化的时间复杂度为 O(nlogn)O(n\log{n})O(nlogn);
获取上一个排列的时间复杂度为 O(n)O(n)O(n)。