要找出数组所有序列中字典序比当前序列大的下一个序列,最差的方法是找出所有序列,分别与当前序列比较。时间复杂符是n!
考虑到要查找的序列只能比当前序列“稍微大一点”,因此应该调整数组右边部分的序列,如果右边部分为“降序”,则继续往左找,直到找到一个数,使得这个数和右边“降序”序列中的其中一个交换,可以得到一个更大的序列
[2,3] //当右边降序序列为[3]时,2小于3,所有交换2,3得到的序列[3,2]更大
[1,3,2] //当右边降序序列为[3,2]时,1小于2,所以交换1,2得到的序列[2,3,1]更大
但是在上面[1,3,2]的例子中,得到的[2,3,1]并不是最终结果,因为3,1是递减的,换成递增可以得到一个比当前序列更小,但仍比原始序列更大的序列,即[2,1,3],所以在交换后需要对右边序列进行一次排序。但是由于一开始我们是在右边序列中,找出比1大的最小的一个元素,也就是2,所以交换后,右边序列仍然是降序的,因此排序只需要反转右边的序列就行,需要O(n)的时间复杂度
- 时间复杂度:O(n)
- 空间复杂度:O(1)