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

难度: Hard

你打算构建一些障碍赛跑路线。给你一个 下标从 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⁷

Submission

运行时间: 170 ms

内存: 32.9 MB

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        # n = len(obstacles)
        # res = [0] * n
        # for i in range(n):
        #     curr = obstacles[i]
        #     dp = []
        #     for j in range(i):
        #         if obstacles[j] <= curr:
        #             if not dp or obstacles[j] >= dp[-1]:
        #                 dp.append(obstacles[j])
        #                 continue
        #             pos = bisect.bisect_right(dp, obstacles[j])
        #             dp[pos] = obstacles[j]
        #     dp.append( obstacles[i])
        #     res[i] = len(dp)

        dp = []
        res = []
        for obs in obstacles:
            if not dp or obs >= dp[-1]:
                dp.append(obs)
                res.append(len(dp))
            else:
                pos = bisect.bisect_right(dp, obs)
                dp[pos] = obs
                res.append(pos+1)

        return res

Explain

题解采用动态规划思路，其中利用了二分查找来优化搜索。对于每个障碍，需要确保它能够在非递减序列中合适地插入以保持序列的有效性。对于每个障碍，如果它比当前序列的最后一个元素大或等于，它将被直接添加到序列的末尾，并且当前的障碍赛跑路线长度加一。如果当前障碍比序列的最后一个元素小，将使用二分查找来找到序列中适当的位置以替换，使得序列仍然保持非递减。结果数组记录了每次操作后的序列长度，反映了到当前位置的最长障碍赛跑路线的长度。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        dp = []  # 初始化动态数组，用于存储非递减序列
        res = []  # 结果数组，记录到每个位置的最长路线长度
        for obs in obstacles:  # 遍历每个障碍
            if not dp or obs >= dp[-1]:  # 如果动态数组为空或当前障碍大于等于数组最后一个元素
                dp.append(obs)  # 直接添加到数组末尾
                res.append(len(dp))  # 将当前数组长度添加到结果数组
            else:
                pos = bisect.bisect_right(dp, obs)  # 二分查找适当的位置来插入当前障碍
                dp[pos] = obs  # 替换找到的位置
                res.append(pos+1)  # 更新结果数组
        return res

Explore

在这个题解中，动态数组`dp`用来维护一个非递减的序列，这是因为该序列的每一个元素代表了在当前障碍点之前可以形成的最长递增子序列的最小可能结尾。这种方法是基于贪心算法的思想：尽可能地让序列保持更小的值，这样能够增加后续元素成为序列一部分的可能性。使用`dp`数组来动态地跟踪每个位置的最优解，使得当后续障碍进来时，可以通过比较和替换来维持或更新这个非递减序列。

在题解中使用`bisect_right`的原因是因为我们需要找到数组中第一个大于当前障碍的位置来进行替换。使用`bisect_right`确保了即使在存在相同元素的情况下，也会返回最右侧（即最后一个相等元素的后一个位置）的索引，这样可以确保替换后数组仍然保持非递减的状态。如果使用`bisect_left`，则在有重复值的情况下可能会替换到一个不合适的位置，破坏已有序列的非递减性质。

在题解的实现中，`dp`数组的更新是通过`bisect_right`找到第一个大于当前障碍的位置，然后用当前障碍替换这个位置的元素来完成的。由于`bisect_right`确保了找到的位置是大于当前障碍的第一个位置，替换后，左侧的元素都是小于或等于当前障碍的，而由于是替换第一个大于当前障碍的元素，右侧的元素自然是大于或等于当前障碍的。这样替换保证了`dp`数组在每次操作后仍然是非递减的。

当连续遇到多个相同的元素时，动态数组`dp`的变化取决于这些元素的位置。对于第一个相同的元素，它可能被添加到`dp`数组的末尾或替换一个较大的值。对于后续相同的元素，由于它们都相同，所以每个都会使用`bisect_right`找到相同的位置进行替换。这意味着`dp`数组的长度不会因为这些相同元素的添加而增加，但其内容可能会在这些位置上更新为相同的值，直到遇到一个更大的值需要再次进行替换或添加。