Jump Game IX
Real-world version: Tallest Reachable Relay TowerThe statement here is our own: the same inputs, outputs and technique.
A line of signal relay towers stands left to right, and heights[i] is the height of tower i. A drone carrying a signal repeater can hop between towers, and from tower i it may hop to tower j when either
j > iandheights[j] > heights[i], so the hop goes to the right and lands on a taller tower, orj < iandheights[j] < heights[i], so the hop goes to the left and lands on a shorter tower.
The two towers of a hop need not be neighbours. The drone may make any number of hops, including none.
For each tower in turn, report the greatest height the drone can be standing on after starting there, counting the starting tower itself. Return those heights in tower order, so the entry at position i belongs to tower i.
Examples
Example 1
- Input
- heights = [12,40,7,25]
- Output
- [40, 40, 40, 40]
From tower 2, height 7, the drone hops right to tower 3, height 25, then left to tower 0, height 12, which is shorter, then right to tower 1, height 40, which is taller. Each of the other starts can reach tower 1 as well, so every answer here is 40.
Example 2
- Input
- heights = [15,60,15]
- Output
- [60, 60, 15]
Tower 0 hops right to tower 1. Tower 2 has nothing to its right, and a left hop needs a strictly shorter tower while both towers to its left are 15 or more, so it stays put and answers with its own height.
Example 3
- Input
- heights = [80,60,40,20]
- Output
- [80, 60, 40, 20]
The heights fall from left to right, so no tower has a taller tower on its right or a shorter tower on its left. Each answer is the tower's own height.
Constraints
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def max_value(heights: list[int]) -> list[int]:public int[] maxValue(int[] heights)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's