package question0031_next_permutation;

/**
 * 时间复杂度是O(n)，其中n为nums数组的长度。空间复杂度是O(1)。
 *
 * 执行用时：1ms，击败100.00%。消耗内存：37.4MB，击败88.12%。
 */
public class Solution {

    public void nextPermutation(int[] nums) {
        int n = nums.length, i = n - 1;
        for (; i >= 1; i--) {
            if (nums[i] > nums[i - 1]) {    //如果存在第i个数比第(i - 1)个数更大的情况，说明存在下一个更大的排列
                break;
            }
        }
        if (i >= 1) {   //存在下一个更大的排列
            int j = n - 1;
            for (; j >= i; j--) {
                if (nums[j] > nums[i - 1]) {    //寻找到比第(i - 1)个数更大的数，其索引是j
                    break;
                }
            }
            swap(i - 1, j, nums);   //交换第(i - 1)个数和第j个数
            reverse(nums, i);   //此时[i, n - 1]仍然是一个降序排列，将其反转为一个升序排列
        } else {    //不存在下一个更大的排列
            reverse(nums, 0);
        }
    }

    private void reverse(int[] nums, int index) {
        int i = index, j = nums.length - 1;
        while (i < j) {
            swap(i, j, nums);
            i++;
            j--;
        }
    }

    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}