LeetCode 31. Next spread

31. Next spread

【 analysis 】 If you want to get an element larger than the current number , We need to exchange the next larger number with the previous smaller number , And the bits exchanged in front should be as low as possible , The numbers exchanged later should be as small as possible , But it has to be bigger than the front . Then it needs to be done in two steps ：

1. Find the position of the previous element to be exchanged .

2. Look for the smallest element larger than him from the back .

about 1, Let's look at a situation 5,4,3,2,1, We find that this number is already the largest arrangement , That is, you can't find the position you can exchange in front . But for permutations 3,5,4,2,1, If you cover up 3, hinder 5,4,2,1 It is already the maximum , however 3 This position can be changed , So it is not difficult to find , When a sequence is arranged in reverse order , His composition is already the maximum . If such two elements are found (i, j),nums[i] < nums[j], Explain that you can change nums[i] To make the element bigger . In this way, we find the minimum bit of the element to be exchanged .

about 2, Suppose the insertion position is i, that [i + 1, n) It must be in descending order , Continue traversing from back to front , Just look for the first element larger than the insertion position , This element is greater than i The smallest element of the element at .

  After exchange , because [i + 1, n) Or in descending order , He is still a big number , But because of the exchange i Cause of , No matter how they are arranged in the back , Are bigger than the previous one , In order to make the result smaller , Also change this part into ascending order .（ You can directly reverse , It's fine too sort）

class Solution {

    //  Monotonic stack  10:12 10:30
    //  Looking back and forth , If it's in ascending order , The description cannot be changed later, for example  4 6 5 3 2 1, We cannot change 65321 From your location 
    //  Find the next one 
    //  however 4 6 It's in reverse order , Explain that you can find a comparison in the back 4 Large element exchange to make the exchange larger than before 
    //  The first ratio found from the back 4 The big one is 5, In exchange for 4 and 5 And then get  5 6 4 3 2 1, But now it's not the smallest element 
    //  It can only be said that 5 The element at the beginning must be larger than that just now 4 At the beginning , So we have to deal with 5 The following elements are arranged in order from small to large 
    //  current  5 1 2 3 4 6 Is the next smallest element 

    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 {

    //  Monotonic stack  10:12 10:30
    //  Looking back and forth , If it's in ascending order , The description cannot be changed later, for example  4 6 5 3 2 1, We cannot change 65321 From your location 
    //  Find the next one 
    //  however 4 6 It's in reverse order , Explain that you can find a comparison in the back 4 Large element exchange to make the exchange larger than before 
    //  The first ratio found from the back 4 The big one is 5, In exchange for 4 and 5 And then get  5 6 4 3 2 1, But now it's not the smallest element 
    //  It can only be said that 5 The element at the beginning must be larger than that just now 4 At the beginning , So we have to deal with 5 The following elements are arranged in order from small to large 
    //  current  5 1 2 3 4 6 Is the next smallest element 

    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;
        }
    }
}