301. Taller to the Right
Pine trees stand in a single row, and a chain of nodes records their heights from the first tree at head to the last. A tree can see the sunrise only if no tree somewhere further along the row is strictly taller than it. Trees of equal height do not block each other.
Remove every node whose height is strictly smaller than the height of at least one node anywhere after it in the chain, and return the head of what is left. The surviving nodes keep their original relative order. The last node always survives, so a non-empty chain never becomes empty. A chain can hold 100,000 nodes, so comparing each node with everything after it is too slow.
Example 1
- Input:
- head = [6,2,9,4,4,1,4]
- Output:
- [9,4,4,4]
- Explanation:
9 is the tallest, so 6 and 2 are removed. The 1 is removed because a 4 follows it. The three 4s are equal, so none blocks another, and the chain becomes 9, 4, 4, 4.
Example 2
- Input:
- head = [-5,-8,-8,-2,-3]
- Output:
- [-2,-3]
- Explanation:
-2 is the tallest from position 4 on, so -5, -8, -8 are removed. -3 is the last node and stays. The result is -2, -3.
Constraints
0 ≤ chain length ≤ 105
-109 ≤ node value ≤ 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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)