// 31. 下一个排列


/*
1、“下一个排列”定义：
  1）给定数字序列的字典序中下一个更大的排列。可以理解成这些数字拼凑成的多个整数，升序排序，然后求当前整数的下一个整数
  2）如果不存在下一个更大的排列，则将数字重新排列成最小的排列。即整数是最大的，那么整体升序排列得到一个最小的整数
2、算法推导
  1）我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数
  2）我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，需要：
    ① 在尽可能靠右的低位进行交换，需要从后向前查找
    ② 将一个尽可能小的「大数」与前面的「小数」交换
    ③ 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列
3、算法过程
  1）从后向前查找第一个相邻升序的元素对 (i-1,i)，满足 A[i-1] < A[i]，即找到第一个可交换的最低位「小数」。此时 [i,end) 必然是降序
  2）在 [i,end) 从后向前查找第一个满足 A[i-1] < A[j] 的 j，即找到第一个可交换的值最小的「大数」。A[i-1]、A[j] 分别是「小数」、「大数」
  3）将 A[i-1] 与 A[j] 交换
  4）此时 [i,end) 必然是降序，逆置 [i,end)，使其升序
  5）如果在步骤1找不到符合的相邻升序元素对，说明当前 [0,end) 为一个降序顺序，即最大的排序，则整体升序得到最小的排列

1   2   3   8   5   7   6   4
                ↑   ↑   ↑
               i-1  i   j
1   2   3   8   6   4   5   7
 */
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }
        for (int i = n - 1; i >= 1; i--) {
            if (nums[i] > nums[i - 1]) {
                for (int j = n - 1; j >= i; j--) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        Arrays.sort(nums, i, n);
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }
}