31. 下一个排列

实现一个算法，找出整数数组中的下一个排列。即字典序比当前排列大的最小排列。

示例：

• 输入：[1,2,3]
  输出：[1,3,2]
• 输入：[3,2,1]
  输出：[1,2,3]
• 输入：[1,1,5]
  输出：[1,5,1]

说明：

1. 整数数组中的元素各不相同。
2. 给定数组始终有效，即始终存在下一个排列。

解题思路：

1. 如果要让一个数尽量大，需要把较大的数字往高位排。
2. 如果一个数组成的数字是由大到小排序，那么这个数就是最大数，它的下个排列，就是最小数。最小数与最大数相反，它数由组成的数字由从小到大排序。
3. 我们希望下一个数 比当前数大，这样才满足 “下一个排列” 的定义。因此只需要 将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
4. 我们还希望下一个数 增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
   • 在尽可能靠右的低位 进行交换，需要 从后向前 查找将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
   • 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

public void nextPermutation(int[] nums) {
        int i = 0;
        int j = 0;
        for (int m = nums.length - 1; m > 0; m--) {
            //1.从右往左找到第一个降序点
            if (nums[m] > nums[m - 1]) {
                i = m - 1;
                j = m;
                break;
            }
        }
        //2.如果整个数组是降序排列，则是最大值。下一个排列，就是最小值，升序排列。
        if (j == 0) {
            Arrays.sort(nums);
            return;
        }
        //3.从右往左的升序中找到一个最小的「大数」往前排序。
        for (int m = nums.length - 1; m > 0; m--) {
            if (nums[m] > nums[i]) {
                swap(nums, i, m);
                //4.把右到左的升序排序成降序，尽量把数字的大小降小
                Arrays.sort(nums, j, nums.length);
                break;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

还有一个题目求上个排列
https://www.lintcode.com/problem/51/

    public List<Integer> previousPermuation(List<Integer> nums) {
        int i = 0;
        int j = 0;
        for (int m = nums.size() - 1; m > 0; m--) {
            //1.从右往左找到第一个升序点
            if (nums.get(m) < nums.get(m - 1)) {
                i = m - 1;
                j = m;
                break;
            }
        }
        //2.如果整个数组是升序排列，则是最小值。下一个排列，就是最大值，降序排列。
        if (j == 0) {
            nums.sort(Comparator.reverseOrder());
            return nums;
        }

        for (int m = nums.size() - 1; m > 0; m--) {
            if (nums.get(m) < nums.get(i)) {
                swap(nums, i, m);
                nums.subList(j, nums.size()).sort(Comparator.reverseOrder());
                break;
            }
        }
        return nums;
    }
    
    public static <T> void swap(List<T> list, int index1, int index2) {
        T temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }