Package g1901_2000.s1964_find_the_longest_valid_obstacle_course_at_each_position

Class Solution

java.lang.Object

g1901_2000.s1964_find_the_longest_valid_obstacle_course_at_each_position.Solution

public class Solution
extends Object

1964 - Find the Longest Valid Obstacle Course at Each Position.<p>Hard</p> <p>You want to build some obstacle courses. You are given a <strong>0-indexed</strong> integer array <code>obstacles</code> of length <code>n</code>, where <code>obstacles[i]</code> describes the height of the <code>i^th</code> obstacle.</p> <p>For every index <code>i</code> between <code>0</code> and <code>n - 1</code> ( <strong>inclusive</strong> ), find the length of the <strong>longest obstacle course</strong> in <code>obstacles</code> such that:</p> <ul> <li>You choose any number of obstacles between <code>0</code> and <code>i</code> <strong>inclusive</strong>.</li> <li>You must include the <code>i^th</code> obstacle in the course.</li> <li>You must put the chosen obstacles in the <strong>same order</strong> as they appear in <code>obstacles</code>.</li> <li>Every obstacle (except the first) is <strong>taller</strong> than or the <strong>same height</strong> as the obstacle immediately before it.</li> </ul> <p>Return <em>an array</em> <code>ans</code> <em>of length</em> <code>n</code>, <em>where</em> <code>ans[i]</code> <em>is the length of the <strong>longest obstacle course</strong> for index</em> <code>i</code> <em>as described above</em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> obstacles = [1,2,3,2]</p> <p><strong>Output:</strong> [1,2,3,3]</p> <p><strong>Explanation:</strong> The longest valid obstacle course at each position is:</p> <ul> <li> <p>i = 0: [1], [1] has length 1.</p> </li> <li> <p>i = 1: [1,2], [1,2] has length 2.</p> </li> <li> <p>i = 2: [1,2,3], [1,2,3] has length 3.</p> </li> <li> <p>i = 3: [1,2,3,2], [1,2,2] has length 3.</p> </li> </ul> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> obstacles = [2,2,1]</p> <p><strong>Output:</strong> [1,2,1]</p> <p><strong>Explanation:</strong> The longest valid obstacle course at each position is:</p> <ul> <li> <p>i = 0: [2], [2] has length 1.</p> </li> <li> <p>i = 1: [2,2], [2,2] has length 2.</p> </li> <li> <p>i = 2: [2,2,1], [1] has length 1.</p> </li> </ul> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> obstacles = [3,1,5,6,4,2]</p> <p><strong>Output:</strong> [1,1,2,3,2,2]</p> <p><strong>Explanation:</strong> The longest valid obstacle course at each position is:</p> <ul> <li> <p>i = 0: [3], [3] has length 1.</p> </li> <li> <p>i = 1: [3,1], [1] has length 1.</p> </li> <li> <p>i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.</p> </li> <li> <p>i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.</p> </li> <li> <p>i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.</p> </li> <li> <p>i = 5: [3,1,5,6,4,2], [1,2] has length 2.</p> </li> </ul> <p><strong>Constraints:</strong></p> <ul> <li><code>n == obstacles.length</code></li> <li><code>1 <= n <= 10⁵</code></li> <li><code>1 <= obstacles[i] <= 10⁷</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int[]	longestObstacleCourseAtEachPosition(int[] obstacles)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

longestObstacleCourseAtEachPosition

public int[] longestObstacleCourseAtEachPosition(int[] obstacles)