A coach writes every possible ordering of the same player numbers in dictionary order: lists
are compared element by element from the left, like words. Given the current lineup nums,
return the lineup that comes immediately before it in that catalogue, as a new list. Orderings
that look identical (because numbers repeat) count only once.
If nums is already the first lineup of the catalogue, wrap around and return the last one
(the numbers in non-increasing order).
Examples
Input: nums = [1, 3, 2]
Output: [1, 2, 3]
Input: nums = [3, 1, 1, 2]
Output: [2, 3, 1, 1]
Explanation: the orderings of 1, 1, 2, 3 in dictionary order end with
..., [2, 3, 1, 1], [3, 1, 1, 2], [3, 1, 2, 1], [3, 2, 1, 1].
Input: nums = [1, 1, 2]
Output: [2, 1, 1]
Explanation: [1, 1, 2] is the first lineup, so the answer wraps to the last one.
Constraints
0 <= len(nums) <= 10**5-10**9 <= nums[i] <= 10**9- Do not modify
nums. - Target: O(n) time. Listing orderings, or rescanning the tail for each position, is far too slow.
Goals
- Find the rightmost place where a smaller arrangement can start
- Pick the right element to swap in when values repeat
- Finish the suffix as large as possible with one reversal