LeetCode 31. 下一个排列

31. 下一个排列

【分析】如果想得到一个比当前数字大的元素，我们需要把后面一个较大的数字和前面一个较小的数字交换，并且前面被交换的位应该尽可能低，后面交换的数字尽可能小，但是得比前面大。那么就需要分两步来了：

1.找到前面要被交换的元素的位置。

2.从后往前找一个比他大的最小元素。

对于1，我们看一种情况5，4，3，2，1，我们发现此时这个数字已经是最大的排列了，也就是无法找到前面可以交换的位置。但是对于排列3，5，4，2，1，如果遮住3，后面的5，4，2，1也已经是极限最大了，但是3这个位置却还可以进行改变，于是不难发现，当一个序列按照逆序排列时，他组成的已经是最大值了。如果发现这样两个元素(i, j)，nums[i] < nums[j]，说明可以通过改变nums[i]来使得元素更大。这样我们就找到了前面要交换的元素的最小位了。

对于2，假设插入位置为i，那么[i + 1, n)一定是按照降序排列，继续从后往前遍历，寻找第一个比插入位置大的元素即可，这个元素就是大于i处元素的最小元素。

 交换完成后，由于[i + 1, n)还是按照降序排列，他还是一个很大的数，但是由于交换i处的缘故，无论后面怎样排列，都比之前那个更大，为了使结果小，还要把这部分改成升序。（可以直接反转，也可以sort）

class Solution {

    // 单调栈 10:12 10:30
    // 从后往前看，如果是升序，说明后面已经无法改变了例如 4 6 5 3 2 1，我们无法通过改变65321的位置来
    // 找下一个
    // 但是4 6是逆序的，说明可以通过在后面找一个比4大的元素交换来使得交换后的比之前大
    // 从后面找到的第一个比4大的是5，交换4和5之后得到 5 6 4 3 2 1，但是现在还不是最小的元素
    // 只能说是以5开头的元素必定大于刚才比4开头的，所以还要对5后面的元素按照从小到大排个序
    // 现在的 5 1 2 3 4 6才是下一个最小的元素

    public void nextPermutation(int[] nums) {
        int n = nums.length, i, j;
        for (i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            Arrays.sort(nums);
            return;
        }
        for (j = n - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                break;
            }
        }
        var t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        Arrays.sort(nums, i + 1, n);
    }
}

class Solution {

    // 单调栈 10:12 10:30
    // 从后往前看，如果是升序，说明后面已经无法改变了例如 4 6 5 3 2 1，我们无法通过改变65321的位置来
    // 找下一个
    // 但是4 6是逆序的，说明可以通过在后面找一个比4大的元素交换来使得交换后的比之前大
    // 从后面找到的第一个比4大的是5，交换4和5之后得到 5 6 4 3 2 1，但是现在还不是最小的元素
    // 只能说是以5开头的元素必定大于刚才比4开头的，所以还要对5后面的元素按照从小到大排个序
    // 现在的 5 1 2 3 4 6才是下一个最小的元素

    public void nextPermutation(int[] nums) {
        int n = nums.length, i, j;
        for (i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i == -1) {
            i = 0; j = n - 1;
            while (i < j) {
                int t = nums[i];
                nums[i++] = nums[j];
                nums[j--] = t;
            }
            return;
        }
        for (j = n - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                break;
            }
        }
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        i++;
        j = n - 1;
        while (i < j) {
            t = nums[i];
            nums[i++] = nums[j];
            nums[j--] = t;
        }
    }
}