The Storm-Masts of Ulvenreach Steppe

The Stormwrights' Guild of Ulvenreach Steppe has raised a single straight line of iron storm-masts across the grass, numbered from west to east. Before the autumn tempests arrive, the Guild is paying a bounty for a reckoning of the line. For every mast, how far east does the nearest mast stand that is strictly taller than it?

Write leapDistances(heights).

heights is a list of non-negative integers. heights[i] is the height of the mast at position i, where position 0 is the westernmost.
Return a list of integers of the same length. Entry i is j - i, where j is the smallest index greater than i with heights[j] > heights[i].
If no mast east of position i is strictly taller, entry i is 0.
A mast of equal height does not count as taller.
An empty heights returns an empty list.

The Guild's lines can run to 100,000 masts, so the reckoning must not grind through every pair.

stacks and queues
Adept

examples

case 1heights of [3, 1, 4, 1, 5]→ [2, 1, 2, 1, 0]. The mast of 3 looks past the 1 to the 4, two places east. The final 5 has nothing taller after it.
case 2heights of [2, 2, 2]→ [0, 0, 0]. Equal masts are not taller, so no mast finds an answer.
case 3heights of [5, 2, 1, 2, 1, 5, 3, 6]→ [7, 4, 1, 2, 1, 2, 1, 0]

reward: 320 XP
signature: leapDistances

not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…

worked example
equal heights never count
empty line
single mast
strictly descending
strictly ascending
mixed with plateaus
long reach past many
zero heights

The Storm-Masts of Ulvenreach Steppe

examples

the bard’s hint