1964. Find the Longest Valid Obstacle Course at Each Position Hard

1/**
2 * [1964] Find the Longest Valid Obstacle Course at Each Position
3 *
4 * 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.
5 * For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:
6 * 
7 * 	You choose any number of obstacles between 0 and i inclusive.
8 * 	You must include the i^th obstacle in the course.
9 * 	You must put the chosen obstacles in the same order as they appear in obstacles.
10 * 	Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.
11 * 
12 * Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.
13 *  
14 * Example 1:
15 * 
16 * Input: obstacles = [1,2,3,2]
17 * Output: [1,2,3,3]
18 * Explanation: The longest valid obstacle course at each position is:
19 * - i = 0: [<u>1</u>], [1] has length 1.
20 * - i = 1: [<u>1</u>,<u>2</u>], [1,2] has length 2.
21 * - i = 2: [<u>1</u>,<u>2</u>,<u>3</u>], [1,2,3] has length 3.
22 * - i = 3: [<u>1</u>,<u>2</u>,3,<u>2</u>], [1,2,2] has length 3.
23 * 
24 * Example 2:
25 * 
26 * Input: obstacles = [2,2,1]
27 * Output: [1,2,1]
28 * Explanation: The longest valid obstacle course at each position is:
29 * - i = 0: [<u>2</u>], [2] has length 1.
30 * - i = 1: [<u>2</u>,<u>2</u>], [2,2] has length 2.
31 * - i = 2: [2,2,<u>1</u>], [1] has length 1.
32 * 
33 * Example 3:
34 * 
35 * Input: obstacles = [3,1,5,6,4,2]
36 * Output: [1,1,2,3,2,2]
37 * Explanation: The longest valid obstacle course at each position is:
38 * - i = 0: [<u>3</u>], [3] has length 1.
39 * - i = 1: [3,<u>1</u>], [1] has length 1.
40 * - i = 2: [<u>3</u>,1,<u>5</u>], [3,5] has length 2. [1,5] is also valid.
41 * - i = 3: [<u>3</u>,1,<u>5</u>,<u>6</u>], [3,5,6] has length 3. [1,5,6] is also valid.
42 * - i = 4: [<u>3</u>,1,5,6,<u>4</u>], [3,4] has length 2. [1,4] is also valid.
43 * - i = 5: [3,<u>1</u>,5,6,4,<u>2</u>], [1,2] has length 2.
44 * 
45 *  
46 * Constraints:
47 * 
48 * 	n == obstacles.length
49 * 	1 <= n <= 10^5
50 * 	1 <= obstacles[i] <= 10^7
51 * 
52 */
53pub struct Solution {}
54
55// problem: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
56// discuss: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/discuss/?currentPage=1&orderBy=most_votes&query=
57
58// submission codes start here
59
60impl Solution {
61    pub fn longest_obstacle_course_at_each_position(obstacles: Vec<i32>) -> Vec<i32> {
62        vec![]
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_1964() {
74    }
75}
76