Index of First Smaller Number to the Right
Given a list of numbers, return the zero-based index of the first strictly smaller number to the right of each number. Return -1 when no smaller number exists to its right.
Method Signature
List<Integer> firstSmallerToRight(List<Integer> nums)
nums contains the numbers in their original order.- Return a list in which the value at index
i is the index of the first smaller number to the right of nums.get(i).
Smaller Number Rules
- An index
j is considered only when j > i and nums.get(j) < nums.get(i).
- If several smaller numbers exist, return the smallest qualifying index
j.
- Equal numbers are not considered smaller.
- Return
-1 if no qualifying index exists.
Required Implementation
- Use a stack-based approach.
- The expected time complexity is
O(n).
- The expected additional space complexity is
O(n).
Constraints
1 ≤ nums.size() ≤ 100,000-1,000,000,000 ≤ nums.get(i) ≤ 1,000,000,000
Examples
Example 1
firstSmallerToRight(nums = [8, 6, 7, 3, 5, 4])
Output: [1, 3, 3, -1, 5, -1]
For example, the first smaller number to the right of 8 is 6 at index 1. No smaller number appears after 3 or the final 4.
Example 2
firstSmallerToRight(nums = [2, 2, 1, 4, 3])
Output: [2, 2, -1, 4, -1]
The two equal values at the beginning are not smaller than each other. Their first smaller number is 1 at index 2.
Example 3
firstSmallerToRight(nums = [1, 3, 5, 7])
Output: [-1, -1, -1, -1]
The numbers are strictly increasing, so no number has a smaller value to its right.