Find the Longest Valid Obstacle Course at Each Position
You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the i^th obstacle.
For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:
- You choose any number of obstacles between
0andiinclusive. - You must include the
i^thobstacle in the course. - You must put the chosen obstacles in the same order as they appear in
obstacles. - Every obstacle, except the first, is taller than or the same height as the obstacle immediately before it.
Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.
Example 1
Input
obstacles = [1,2,3,2]Output
[1,2,3,3]The longest valid obstacle courses at indices 0 through 3 have lengths 1, 2, 3, and 3 respectively, with
[1, 2, 2] valid at index 3.Example 2
Input
obstacles = [2,2,1]Output
[1,2,1]The longest valid obstacle courses at indices 0, 1, and 2 are
[2], [2, 2], and [1], with lengths 1, 2, and 1 respectively.Constraints
- n == obstacles.length
- 1 <= n <= 10^5
- 1 <= obstacles[i] <= 10^7