322. Next Bigger Link
A ski resort records the height of each marker along a single-file trail, and the markers are stored as a chain: every node holds a height and a link to the next marker downhill. For each marker, the guide wants to know the first marker further along the trail that is strictly taller than it.
Given the head of the chain, return an array with one entry per node, in chain order. The entry for a node is the height of the nearest later node whose value is strictly greater than that node's value, or 0 if no such node exists. Every height is a positive integer, so 0 can never be mistaken for a real answer. The chain can hold up to 100,000 nodes, so rescanning the rest of the chain from every node will be too slow.
Example 1
- Input:
- head = [7,3,9,2,2,8]
- Output:
- [9,9,0,8,8,0]
- Explanation:
7 is followed by 3 and then 9, so its answer is 9; 3 also sees 9 first; 9 and the final 8 have nothing taller after them; both 2s see 8 as the first taller value. Result: [9, 9, 0, 8, 8, 0].
Example 2
- Input:
- head = [4,4,6,1,5]
- Output:
- [6,6,0,5,0]
- Explanation:
Equal values do not count as bigger, so both 4s answer 6. The 1 answers 5, while 6 and 5 have no taller node later. Result: [6, 6, 0, 5, 0].
Constraints
0 ≤ chain length ≤ 105
1 ≤ 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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)