402. Rounds to Non-Decreasing
A conveyor belt carries parcels, and nums[i] is the weight of the parcel at position i. In every round, a robot looks at the belt and, at the same moment, removes every parcel that is strictly lighter than the parcel directly before it (using the belt as it was at the start of that round). The remaining parcels close up, and the next round starts.
Return the number of rounds the robot works until no parcel is lighter than its predecessor, that is, until the belt is sorted in non-decreasing order. If the belt is already sorted the answer is 0. Simulating every round can take O(n^2) time, so look for a way to compute, for each parcel, in which round it disappears.
Example 1
- Input:
- nums = [10,3,8,1,9,2,2]
- Output:
- 3
- Explanation:
Round 1 removes 3, 1 and 2 (the first one) leaving [10, 8, 9, 2]. Round 2 removes 8 and 2 leaving [10, 9]. Round 3 removes 9. Three rounds.
Example 2
- Input:
- nums = [2,2,5,9]
- Output:
- 0
- Explanation:
The belt is already non-decreasing, so no round is needed.
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)