What is the main pattern in Find the Longest Valid Obstacle Course at Each Position?

The main pattern is using binary search over the valid answer space to track the longest non-decreasing sequence ending at each index.

Can I solve this problem without binary search?

Yes, a naive O(n^2) approach using nested loops works but is inefficient for large n and exceeds time limits.

How do repeated obstacle heights affect the sequence?

Repeated heights can extend the non-decreasing sequence, so the tracking array must allow equal values in binary search.

What data structure helps optimize this problem?

An array storing the minimum ending height for each possible course length allows efficient binary search and updates.

Is this problem related to Longest Increasing Subsequence?

Yes, it generalizes LIS with non-decreasing sequences and requires tracking sequences ending at each position rather than overall maximum length.

#1964

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找出到每个位置为止最长的有效障碍赛跑路线

你打算构建一些障碍赛跑路线。给你一个下标从 0 开始的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1 ）的下标 i ，在满足下述条件的前提下，请你找出 obstacle…

数组二分查找树状数组

题目描述

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
在这条路线中，必须包含第 i 个障碍。
你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍相同或者更高。

返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

示例 1：

输入：obstacles = [1,2,3,2]
输出：[1,2,3,3]
解释：每个位置的最长有效障碍路线是：
- i = 0: [1], [1] 长度为 1
- i = 1: [1,2], [1,2] 长度为 2
- i = 2: [1,2,3], [1,2,3] 长度为 3
- i = 3: [1,2,3,2], [1,2,2] 长度为 3

示例 2：

输入：obstacles = [2,2,1]
输出：[1,2,1]
解释：每个位置的最长有效障碍路线是：
- i = 0: [2], [2] 长度为 1
- i = 1: [2,2], [2,2] 长度为 2
- i = 2: [2,2,1], [1] 长度为 1

示例 3：

输入：obstacles = [3,1,5,6,4,2]
输出：[1,1,2,3,2,2]
解释：每个位置的最长有效障碍路线是：
- i = 0: [3], [3] 长度为 1
- i = 1: [3,1], [1] 长度为 1
- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2

提示：

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

lightbulb

解题思路

方法一：树状数组

我们可以用树状数组维护一个最长递增子序列的长度数组。

然后对于每个障碍，我们在树状数组中查询小于等于当前障碍的最长递增子序列的长度，假设为 $l$ ，那么当前障碍的最长递增子序列的长度为 $l+1$ ，我们将 $l+1$ 添加到答案数组中，并将 $l+1$ 更新到树状数组。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为障碍的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s = max(s, self.c[x])
            x -= x & -x
        return s


class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        nums = sorted(set(obstacles))
        n = len(nums)
        tree = BinaryIndexedTree(n)
        ans = []
        for x in obstacles:
            i = bisect_left(nums, x) + 1
            ans.append(tree.query(i) + 1)
            tree.update(i, ans[-1])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) if using binary search for each obstacle to find its place in the tracking array. Space complexity is O(n) to store the tracking array and the result ans.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a binary search solution to handle large input sizes efficiently.
question_mark
Consider how to maintain minimum heights per course length to extend sequences correctly.
question_mark
Watch for edge cases where obstacles decrease or repeat, impacting sequence length.

warning

常见陷阱

外企场景

error
Failing to maintain the minimum height for each course length can produce shorter sequences than possible.
error
Using linear scan instead of binary search leads to TLE on large inputs.
error
Incorrectly updating the tracking array can overwrite valid sequences and reduce the final answer.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest strictly increasing obstacle course at each position.
arrow_right_alt
Compute the total number of distinct valid obstacle courses ending at each index.
arrow_right_alt
Determine the maximum obstacle course length if only adjacent elements can be used.

help

常见问题

外企场景

继续练习

#2179 统计数组中好三元组数目 #2250 统计包含每个点的矩形数目 #1649 通过指令创建有序数组