数组与哈希中等1 种解法
#31下一个排列
原地把数组改为字典序中的下一个排列；若已是最大排列则改为最小排列。
#数组#双指针#排列
原题
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,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 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
解题主线
- 从右向左找到首个 nums[pivot] < nums[pivot + 1]，其右侧必为非递增后缀。
- 用后缀中最右侧且大于 pivot 的值交换，再反转后缀即可得到最小增量。
解法 1：枢轴交换 + 后缀反转
定位可增大的最右位置，以后缀中的最小更大值替换，再把后缀恢复为升序。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public void nextPermutation(int[] nums) {
// 枢轴右侧保持非递增；枢轴是最靠右的可增大位置。
int pivot = nums.length - 2;
while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) pivot--;
if (pivot >= 0) {
// 从末尾找到最小的更大值，使字典序增量尽可能小。
int successor = nums.length - 1;
while (nums[successor] <= nums[pivot]) successor--;
swap(nums, pivot, successor);
}
// 反转非递增后缀得到升序；无枢轴时会反转整个数组。
reverse(nums, pivot + 1, nums.length - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) swap(nums, left++, right--);
}
private void swap(int[] nums, int left, int right) {
int temporary = nums[left];
nums[left] = nums[right];
nums[right] = temporary;
}
}边界与易错点
- 全数组非递增时 pivot 为 -1，应直接反转整个数组。
- 交换对象必须是后缀中最右侧的大于 pivot 的元素。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q031_nextPermutation.java