Removal Order of Valid Numbers
You are given a list of integers. Repeatedly remove valid numbers and return them in the order in which they are removed.
Valid Number
- A number is valid if it is strictly greater than both of its current neighbors.
- For the first number, treat its missing left neighbor as
Integer.MIN_VALUE.
- For the last number, treat its missing right neighbor as
Integer.MIN_VALUE.
- A list containing one number treats both neighbors as
Integer.MIN_VALUE.
Removal Rules
- Find all valid numbers in the current list.
- Remove and return the smallest valid number.
- If the smallest valid value occurs at multiple valid positions, remove the occurrence having the lowest current index.
- After removing a number, its left and right neighbors become adjacent.
- Continue until every number has been removed.
Method Signature
List<Integer> findValidNumberOrder(List<Integer> numbers)
numbers is the list whose numbers must be removed.- The method returns the numbers in their removal order.
- The input list does not need to be modified.
Constraints
1 ≤ numbers.size() ≤ 100,000-2,147,483,647 ≤ numbers.get(i) ≤ 2,147,483,647- The input guarantees that at least one valid number exists after every removal until the list becomes empty.
Examples
Example 1
findValidNumberOrder(numbers = List.of(3, 1, 4, 2))
Output: List.of(3, 4, 2, 1)
- Initially,
3 and 4 are valid, so the smaller value 3 is removed.
- The remaining list is
[1, 4, 2], so 4 is removed.
- The remaining numbers are then removed in the order
2, 1.
Example 2
findValidNumberOrder(numbers = List.of(7, 5, 3, 1))
Output: List.of(7, 5, 3, 1)
In each iteration, the first number is greater than its right neighbor and its missing left neighbor.
Example 3
findValidNumberOrder(numbers = List.of(4, 1, 4, 2))
Output: List.of(4, 4, 2, 1)
Both occurrences of 4 are initially valid and equal, so the occurrence at the lower current index is removed first.