力扣hot100 下一个排列 双指针 找规律

Problem: 31. 下一个排列

🌸思路

👨?🏫 参考题解

🌸 Code

class Solution {
	public void nextPermutation(int[] nums)
	{
		int n = nums.length;
		if (n <= 1)
			return;
		int idx = n - 2;// 前指针
		int j = n - 1;// 后指针
//		从后向前 查找第一个 相邻升序 的元素对 (left,j)
//		找到：nums[idx] < nums[j] 前边第一个较小的数（例：123654 中的 3 [idx指针记录 3 的下标]）
		while (idx >= 0 && nums[idx] >= nums[j])
		{
			idx--;
			j--;
		}

//		此时 [idx,n) 区间是降序区间		
//		在 [idx,end) 从后向前 查找第一个满足 A[i] < A[j] 的 j (后面较大的数)
		j = n - 1;
		if (idx >= 0)
		{
//			找到：nums[left] < nums[j] 
			while (nums[idx] >= nums[j])
				j--;
//			后边较大的数 和 前边较小的数 交换
			int t = nums[idx];
			nums[idx] = nums[j];
			nums[j] = t;
		}

//		(idx,n) 开区间改为升序
		int l = idx + 1;
		j = n - 1;
		while (l < j)
		{
//			经典双指针交换
			int t = nums[l];
			nums[l] = nums[j];
			nums[j] = t;
			l++;
			j--;
		}
	}
    
    
}