解题思路“下一个排列”定义给定数字序列将其重新排列成字典序中下一个更大的排列。如果不存在更大的排列即当前排列已经是最大如降序排列则将其重新排列为最小的排列升序排列。算法步骤如下从右向左找到第一对相邻的升序对 (i, i1)满足 nums[i] nums[i1]。此时 i 是需要调整的位置因为 i1 到末尾的子序列一定是降序的否则会更早找到升序对。如果找到了这样的 i· 从右向左找到第一个大于 nums[i] 的元素 nums[j]。· 交换 nums[i] 和 nums[j]。将 i1 到末尾的子序列反转因为该子序列是降序反转后变成升序得到最小的排列。如果没有找到 i整个数组是降序说明当前已是最大排列直接反转整个数组即可。该算法只需常数额外空间时间复杂度为 O(n)。Java 代码实现classSolution{publicvoidnextPermutation(int[]nums){intnnums.length;if(n1)return;// 1. 从右向左找到第一个升序对intin-2;while(i0nums[i]nums[i1]){i--;}// 2. 如果找到了 i则在右侧找一个比 nums[i] 大的最小元素并交换if(i0){intjn-1;while(jinums[j]nums[i]){j--;}swap(nums,i,j);}// 3. 反转 i1 到末尾的部分若 i -1 则反转整个数组reverse(nums,i1,n-1);}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}privatevoidreverse(int[]nums,intstart,intend){while(startend){swap(nums,start,end);start;end--;}}}复杂度分析· 时间复杂度O(n)最多扫描数组两次找 i 和 j以及一次反转。· 空间复杂度O(1)仅使用常数个变量原地修改数组。