Idea:

- Find the index "sortIdx" after which the numbers are sorted in descending order.
- Find the index "swapIdx" which is the least number greater than nums[sortIdx-1] after sortIdx. (That is the last index greater than nums[sortIdx-1] since the subarray after sortIdx is sorted in descending order.)
- Swap sortIdx-1 and swapIdx-1.
- Reverse the subarray after sortIdx.

```
public class Solution {
public void nextPermutation(int[] nums) {
if(nums==null || nums.length<=1) return;
final int N = nums.length;
int sortIdx = N-1; // numbers after sortIdx (include) is sorted in descending order
for(int i=N-1; i>=1 && nums[i]<=nums[i-1]; i--){
sortIdx--;
}
if(sortIdx>0){
int swapIdx = N;
for(int i=N-1; i>=sortIdx && nums[i]<=nums[sortIdx-1]; i--){
swapIdx = i;
}
swap(nums, sortIdx-1, swapIdx-1);
}
reverse(nums, sortIdx, N-1);
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int i, int j){
while(i<j){
swap(nums, i, j);
i++; j--;
}
}
}
```