题目: 下一个排列

分析

所谓的字典序是指字符按照从小到大进行排列，所以排列中最小的字典序排列是数组中的数字都是从小到大进行排列的，而排列中最大的字典序排列是指数组中的数字都是从大到小进行排列。

如果该排列已经最大的字典序排列，即改排列中数组的数字是依此减小的，则直接输出最小的字典序排列即可。

如果该排列不是最大的字典序排列：

因为字典序排列越是靠前位置的数字权重越大，反之靠后位置的数字权重较小，要找到输入的排列中下一个排列，需要从后向前进行循环处理，如果从后向前的数字都是升序直到循环结束，则该排列是最大的字典序排列。

如果在从后向前循环处理的过程中，第一次出现了非递增的连续两个数字 a_i 和 a_i-1 ，则说明该序列有下一个更大的字典序，因为后面的序列都已经是递增的序列，所以将非递增数字的前面的那个数字a_i-1交换为后面数字中比a_i-1大的数字中的最小数字，再将后面的数字按照从小到大进行排列就是比当前排列大的下一个排列，

字典序

算法流程

将数组用 a₀, a₁, a₂, a₃, ... , a_n-1, a_n进行表示。

从 a_n 开始比较相邻的两个数字，比如是 a_i 和a_i-1,如果a_i-1 >= a_i ，则减小 i 的值继续向前比较。

如果循环到i = 1依然满足a₀ > a₁，则说明该序列是最大的排列，那么输出最小的排列即可，可以将该数组进行反转实现输出最小的排列。

如果循环过程中发生了a_i-1 < a_i ，则说明存在字典序更大的排列，查找 a_i 到 a_n 中比a_i-1大的数字中的最小数字，比如为 a_j。

将 a_i-1 和 a_j 进行交换。

将 a_i 到 a_n 之间的数字进行升序排序。

复杂度

字典序的时间复杂度是O（n）。

题解

字典序

import java.util.Arrays;

public class Solution {
    public void solute(int[] res) {
        int i = res.length - 1;
        while (res[i - 1] >= res[i]) {
            i--;
        }
        i--;
        int j = i + 1;
        while (j < res.length && res[j] >= res[i]) 
            j++;
        j--;
        swap(res, i, j);
        Arrays.sort(res, i + 1, n);
    }

    static boolean swap(int[] res, int i, int j) {
        if (i == j) return false;
        int tem = res[i];
        res[i] = res[j];
        res[j] = tem;
        return true;
    }
}