题目链接：31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com)

看看这个链接！评论区有人API一把梭…不行 我用的是Java

理解题解：两轮从尾部开始的扫描，第一轮找出第一个顺序对nums[i], nums[i+1]，以此为分界，之后为倒序。第二轮找出后面倒序的部分里从后往前第一个大于nums[i]的元素nums[j]，和nums[i]交换。此时后面还是倒序（因为nums[j]>nums[i]，nums[j+1]<nums[i]， nums[j-1]>nums[j]），所以只要用双指针往中央扫描、前后交换的方式排一下序就好了。一共涉及三次扫描操作，复杂度O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1]) {
            --i; 
        }
        if(i >= 0) {
            int j = nums.length - 1;
            while(j >= i+1 && nums[j] <= nums[i]) {
                --j;
            }
            swap(nums, i, j);
        }
        reverse(nums, i+1);
    }

    public void swap(int[] nums, int i, int j) {
        // easy
    }

    public void reverse(int[] nums, int begin) {
        int left = begin, right = nums.length-1;
        while(left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}