To make the permutation larger, we could increase any nums[i]. Once nums[i] is increased, the the order of left part should be the smallest to get the exact next permutation.
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
if nums == list(sorted(nums, reverse=True)):
nums.sort()
return
# Find the largest i where nums[i] < nums[i + 1]
for i in range(len(nums) - 2, -1, -1):
if nums[i] < nums[i + 1]:
break
# Find the smallest j where j > i and nums[j] > nums[i]
smallest_j = i + 1
for j in range(i + 2, len(nums)):
if nums[j] <= nums[i]:
break
if abs(nums[j] - nums[i]) < abs(nums[smallest_j] - nums[i]):
smallest_j = j
j = smallest_j
# switch i, j
nums[i], nums[j] = nums[j], nums[i]
# Sort left part
for num, k in zip(sorted(nums[i + 1:]), range(i + 1, len(nums))):
nums[k] = num