下一个排列
题目链接
下一个排列
题目描述
注意点
- 必须 原地 修改，只允许使用额外常数空间
- 如果不存在一个字典序更大的排列，则返回字典序最小的排列
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
解答思路
- 找到下一个配列的关键是找到比当前字典序更大的字典序，同时要保证字典序的增幅最小（不存在字典序更大的特殊情况除外）
- 怎样找到增幅最小的更大字典序？观察规律可得，要保证字典序更大，需要将数组中前面某个较小的数字与后面某个较大的数字进行交换；要保证增幅更大，则需要从后往前找到第一个nums[i] < nums[i + 1]的数nums[lastMin]，再从后往前找到第一个比nums[lastMin]大的数比nums[lastMax]大的数，将两个数进行交换，随后将lastMin左侧的数组变为升序排列即可（此时左侧的数组一定按降序排列）
- 需要特殊考虑的是，如果此时数组已经是最大字典序，则下一个排列是最小字典序，此时数组是降序排列的，只需要将数组改为升序排列即可
代码
class Solution {public void nextPermutation(int[] nums) {int n = nums.length;// 从后往前找到第一个nums[i] < nums[i + 1]的数int lastMin = n - 2;while (lastMin >= 0 && nums[lastMin] >= nums[lastMin + 1]) {lastMin--;}// 如果数组非递减，从后往前第一个比nums[lastMin]大的数，与nums[lastMin]进行交换if (lastMin >= 0) {int lastMax = n - 1;while (lastMax > lastMin && nums[lastMax] <= nums[lastMin]) {lastMax--;}swap(nums, lastMin, lastMax);}// 将left右侧的数组改为升序（此时必定为降序）int left = lastMin + 1;int right = n - 1;while (left < right) {swap(nums, left, right);left++;right--;}}public void swap(int[] nums, int left, int right) {int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;}
}
关键点
- 怎么找到下一个排列
- 最大字典序的下一个排列特殊考虑