自己解法

这个题的思路就是从后往前，找到不是升序排列的节点，然后去找已遍历过的元素中，第一个比这个节点大的，两者进行交换。交换完之后，再对后半段元素进行反转排序，这个自己写的时候忘记了。如果本身元素从头到尾就是降序排列的，就直接反转，取最小排列。时间复杂度为O(n),空间复杂度为O（1），没使用额外的空间。

class Solution {

    public void nextPermutation(int[] nums) {

        if (nums.length == 0 || nums.length == 1) {

            return;

        }

        for (int i = nums.length - 1; i > 0; i--) {

            // 找到不是降序的切入点

            if (nums[i] > nums[i - 1]) {

                int left = i - 1;

                int right = nums.length - 1;

                for (int j = nums.length - 1; j >= i; j--) {

                    if (nums[j] > nums[left]) {

                        right = j;

                        break;

                    }

                }

                int temp = nums[left];

                nums[left] = nums[right];

                nums[right] = temp;

                // left后面的内容要进行反转才是最小

                reverse(nums, ++left, nums.length - 1);

                return;

            }

        }

        // 上面一直没处理的话，说明数组内原本都是降序的，进行全反转

        reverse(nums, 0, nums.length - 1);

    }

    private void reverse(int[] nums, int start, int end) {

        while (start < end) {

            int temp = nums[start];

            nums[start] = nums[end];

            nums[end] = temp;

            start++;

            end--;

        }

    }

}

官方解法

思路一致，但写法更简洁，找出不是降序排序的节点，直接找出就好，不用在循环里处理后续的逻辑，最后这个反转，直接用i + 1,包括了交换后反转交换节点后面的逻辑，以及未交换时，反转整个数组的逻辑。

public class Solution {

    public void nextPermutation(int[] nums) {

        int i = nums.length - 2;

        while (i >= 0 && nums[i + 1] <= nums[i]) {

            i--;

        }

        if (i >= 0) {

            int j = nums.length - 1;

            while (j >= 0 && nums[j] <= nums[i]) {

                j--;

            }

            swap(nums, i, j);

        }

        reverse(nums, i + 1);

    }

    private void reverse(int[] nums, int start) {

        int i = start, j = nums.length - 1;

        while (i < j) {

            swap(nums, i, j);

            i++;

            j--;

        }

    }

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}