0031.下一个排列

https://leetcode.cn/problems/next-permutation/

方法一：两边扫描

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func nextPermutation(nums []int) {
	l, r := len(nums)-2, len(nums)-1
	for l >= 0 && nums[l] >= nums[l+1] {
		l--
	}
	for l >= 0 && r > l && nums[r] <= nums[l] {
		r--
	}
	if l >= 0 && r >= 0 {
		nums[l], nums[r] = nums[r], nums[l]
	}
	for i, j := l+1, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        let (l, r) = (nums.len() - 2, nums.len() - 1);
        let (mut l, mut r) = (l as i32, r as i32);
        while l >= 0 && nums[l as usize] >= nums[l as usize + 1] {
            l -= 1;
        }
        while l >= 0 && r > l && nums[r as usize] <= nums[l as usize] {
            r -= 1;
        }
        if l >= 0 {
            nums.swap(l as usize, r as usize);
        }
        let (mut l, mut r) = (l as usize + 1, nums.len() - 1);
        while l < r {
            nums.swap(l, r);
            l += 1;
            r -= 1;
        }
    }
}