Standard Bar Arrays · Medium O(n) · O(1) auxiliary (excluding the output)
A survey drone records the elevation of each waypoint along a ridge as a list of positive integers. Waypoints that are higher than or equal to every waypoint after them act as visible vantage points and must be reported. The list of vantage points is expected in the same left-to-right order as the ridge.
Input: An integer n followed by an array A of n positive integers.
Output: The values that are greater than or equal to every element to their right, in the original left-to-right order. The last element always qualifies.
1 <= n <= 10^61 <= A[i] <= 10^9Input: {"n":6,"A":[16,17,4,3,5,2]}
Output: [17,5,2]
17 dominates everything to its right, 5 beats 2, and the final waypoint is always a vantage point.
Input: {"n":4,"A":[5,4,3,2]}
Output: [5,4,3,2]
The ridge descends the whole way, so every waypoint is at least as high as all the ones after it.