31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

题目翻译：
一个整数数组的排列是将其元素按顺序或线性顺序排列。

例如，对于arr = [1,2,3]，以下是arr的所有排列：[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]。
整数数组的下一个排列是按字典序排列的下一个排列。更正式地说，如果数组的所有排列都按照字典序排列在一个容器中，那么该数组的下一个排列就是在排序容器中紧跟其后的排列。如果无法进行这样的安排，则必须将数组重新排列为最低可能顺序（即，按升序排序）。

例如，arr = [1,2,3]的下一个排列是[1,3,2]。
同样，arr = [2,3,1]的下一个排列是[3,1,2]。
而arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]没有字典序更大的重排。
给定一个整数数组nums，找到nums的下一个排列。

替换必须在原地进行，只使用常量额外内存。

class Solution {
    public void nextPermutation(int[] nums) {
        // 从后向前遍历，寻找第一个升序的相邻元素对
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找到了升序的相邻元素对
        if (i >= 0) {
            // 从后向前遍历，寻找第一个大于nums[i]的元素
            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            // 交换nums[i]和nums[j]
            swap(nums, i, j);
        }

        // 将nums[i + 1]之后的元素反转（升序排列）
        reverse(nums, i + 1, nums.length - 1);
    }

    // 交换数组中两个元素的位置
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 反转数组中指定区间的元素
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}