Ring road beacons
EasyOnline Assessment
Find the towers that can serve as beacons along a ring road.
The towers stand around a circular road, listed in order in heights: tower i is next to tower i - 1 and tower i + 1, and the road closes on itself, so the last tower is next to the first. A tower is a beacon when it is strictly taller than both of its neighbours. A tower that merely ties a neighbour is not a beacon.
When there are only two towers, each one has the other as both neighbours. A single tower has no other tower to be taller than, so it is not a beacon.
Input: heights, a list of positive integers.
Output: a list of integers, the indices of all beacons in increasing order. If there are none (or heights is empty), return [].
Example 1
- Input:
- [[3,7,2,9,4]]
- Output:
- [1,3]
- Explanation
- Tower 1 (height 7) is taller than 3 and 2, and tower 3 (height 9) is taller than 2 and 4. Tower 0 has neighbours 4 (wrapping from the end) and 7, so it loses to 7. Tower 4 has neighbours 9 and 3 (wrapping), so it loses to 9. Answer
[1, 3].
Example 2
- Input:
- [[8,2,5,1,6]]
- Output:
- [0,2]
- Explanation
- Tower 0 (height 8) is taller than its neighbours 6 (the last tower, by wrapping) and 2, so it is a beacon even though it is at the start of the list. Tower 2 (5) beats 2 and 1. Tower 4 (6) beats 1 but not its wrap-around neighbour 8. Answer
[0, 2].
Example 3
- Input:
- [[4,4,1,4]]
- Output:
- []
- Explanation
- Towers 0 and 1 are tied at 4, and so are towers 3 and 0 (wrapping): a tower that only equals a neighbour is not strictly taller. No beacons.
Constraints
0 <= heights.length <= 10,0001 <= heights[i] <= 1,000,000