1964.Find the Longest Valid Obstacle Course at Each Position

tags: `Hard`,`Array`,`Binary Search`

1964. 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 0 and i inclusive.
You must include the i^th obstacle 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]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.

Example 2:

Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.

Example 3:

Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.

Constraints:

n == obstacles.length
1 <= n <= 10⁵
1 <= obstacles[i] <= 10⁷

解答

Python












class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        tmp = []
        ans = []
        for obstacle in obstacles:
            target = bisect_right(tmp, obstacle)
            if target == len(tmp):
                tmp.append(obstacle)
            else:
                tmp[target] = obstacle
            ans.append(target + 1)
        return ans

Yen-Chi ChenSun, May 7, 2023

Javascript













import _ from 'lodash';

function longestObstacleCourseAtEachPosition(obstacles) {
  const ans = [];
  const tail = [];
  for (const num of obstacles) {
    const index = _.sortedLastIndex(tail, num);
    tail[index] = num;
    ans.push(index + 1);
  }

  return ans;
}

學到很多，其實這題就是找最長非遞減子序列，看答案才恍然大悟，就是LIS的變形而已。
MarsgoatMon, May 8, 2023

Reference

回到題目列表