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

你打算构建一些障碍赛跑路线。给你一个 下标从 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 <= 105
• 1 <= obstacles[i] <= 107

方法一：动态规划 + 二分查找

思路与算法

本题和「300. 最长递增子序列」 是几乎一样的题目。

可以发现，我们需要求出的是数组 obstacles 中以每一个下标为结束位置的「最长递增子序列」的长度，其中「递增」表示子序列中相邻两个元素需要满足前者小于等于后者。而 300 题需要求出的是数组中的「最长严格递增子序列」，我们只需要修改比较两个元素的大小关系的逻辑（将「小于等于」改成「小于」，反之亦然），就可以实现这两种问题之间的相互转换。

由于在求解「最长严格递增子序列」的过程中，是需要求出以每一个下标为结束位置的「最长严格递增子序列」的长度的，因此我们可以直接使用「300. 最长递增子序列」的官方题解 中方法二的代码。如果读者对该方法不熟悉，可以阅读官方题解或者其它参考资料进行学习，本题解不再赘述。

代码

下面的代码直接修改自 「300. 最长递增子序列」的官方题解 中方法二的 Python 代码。

[sol1-C++]

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> d, ans;
        for (int ob: obstacles) {
            // 这里需要改成 >=
            if (d.empty() || ob >= d.back()) {
                d.push_back(ob);
                ans.push_back(d.size());
            }
            else {
                // 将 300 题解中的二分查找改为 API 调用使得代码更加直观
                // 如果是最长严格递增子序列，这里是 lower_bound
                // 如果是最长递增子序列，这里是 upper_bound
                int loc = upper_bound(d.begin(), d.end(), ob) - d.begin();
                ans.push_back(loc + 1);
                d[loc] = ob;
            }
        }
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        d = list()
        ans = list()
        for ob in obstacles:
            # 这里需要改成 >=
            if not d or ob >= d[-1]:
                d.append(ob)
                ans.append(len(d))
            else:
                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观
                # 如果是最长严格递增子序列，这里是 bisect_left
                # 如果是最长递增子序列，这里是 bisect_right
                loc = bisect_right(d, ob)
                ans.append(loc + 1)
                d[loc] = ob
        
        return ans

复杂度分析

• 时间复杂度：O(n \log n)。

• 空间复杂度：O(n)。