【LeetCode】动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线（附完整Python/C++代码）

动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线

前言
题目描述
基本思路
Python代码
- - Python代码解释总结：
C++代码
- - C++代码解释总结：
总结

前言

最长有效障碍物路线问题 是一个涉及到 最长递增子序列（LIS） 变种的问题。给定一个障碍物高度的数组，要求在每个位置找到一个最长有效的障碍物路线，满足在该位置的障碍物高度必须大于或等于之前路线中的最大高度。这个问题结合了 动态规划 和 二分查找 的思想，我们可以使用这些算法来高效地求解该问题。

题目描述

【LeetCode】动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线（附完整Python/C++代码）-LMLPHP

基本思路

1. 问题定义

给定一个数组 obstacles，数组中每个元素表示障碍物的高度。对于每个位置 i，我们需要找到一个最长的障碍物路线（到当前位置为止），满足路线中每个位置的障碍物高度都不超过当前位置的障碍物高度。

2. 理解问题和递推关系

这个问题本质上是一个变种的 LIS（最长递增子序列） 问题，但与传统的 LIS 不同的是，这里允许相等的元素。要求在每个位置 i 处计算到该位置的最长有效障碍物路线长度。可以用类似 LIS 的方式解决该问题，并利用 二分查找 优化。

动态规划递推公式：

定义一个数组 dp，其中 dp[i] 表示从第一个位置到第 i 个位置的最长有效障碍物路线的长度。
设 tails 数组用于维护当前最长有效障碍物路线的最小结尾值。对于每个 obstacles[i]，我们在 tails 中找到最右边的一个值，使得其小于等于 obstacles[i]，然后更新这个值或扩展 tails 数组。

公式推导：

初始化一个空的 tails 数组，用于存储障碍物的递增序列的结尾。
对于每一个 obstacles[i]：
- 使用二分查找找到 tails 中第一个大于 obstacles[i] 的位置 pos。
- 如果 pos 是有效的索引，则替换 tails[pos] 为 obstacles[i]。
- 如果 pos 超出了 tails 的长度，则将 obstacles[i] 追加到 tails 的末尾。
- 更新 dp[i] = pos + 1，表示在位置 i 处的最长障碍物路线长度。

伪代码：

initialize empty tails array
for each obstacle in obstacles:
    find position pos using binary search where tails[pos] > obstacle
    if pos is valid:
        update tails[pos] with current obstacle
    else:
        append obstacle to tails
    set dp[i] = pos + 1
return dp array

核心思想：

通过维护一个 tails 数组，来跟踪有效的障碍物路线，使用二分查找优化搜索位置。
dp[i] 记录每个位置的最长有效障碍物路线的长度。

3. 解决方法

动态规划 + 二分查找

初始化一个空的 tails 数组，用于存储当前的有效障碍物路线。
对每一个 obstacles[i]，通过二分查找找到可以替换的位置或追加的位置，然后更新 dp[i]。
最终 dp 数组即为每个位置的最长有效障碍物路线。

4. 进一步优化

通过使用二分查找，动态维护 tails 数组的最小结尾值，可以将动态规划的时间复杂度从 O(n^2) 降低到 O(n log n)。这种优化适用于处理大规模数据。

5. 小总结

本问题的核心思想是利用 LIS 的变种来解决障碍物路线问题。
通过动态规划和二分查找的结合，可以在 O(n log n) 的时间复杂度内高效地找到每个位置的最长有效障碍物路线。

以上就是的基本思路。

Python代码

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: list[int]) -> list[int]:
        tails = []  # tails用于存储递增序列的末尾值
        dp = []  # dp用于记录每个位置的最长有效路线长度
        
        for i, obstacle in enumerate(obstacles):
            # 找到可以插入的位置，使用bisect_right允许相等的元素
            pos = bisect_right(tails, obstacle)
            
            if pos < len(tails):
                tails[pos] = obstacle  # 替换该位置的值
            else:
                tails.append(obstacle)  # 如果没有合适位置，则追加
            
            dp.append(pos + 1)  # dp[i]表示以obstacles[i]结尾的最长有效路线
        
        return dp

Python代码解释总结：

二分查找：通过 bisect_right 找到 tails 数组中第一个大于当前 obstacle 的位置。
更新 tails 数组：如果找到位置 pos，则更新该位置的值为当前障碍物高度；如果没找到位置，则将当前障碍物高度追加到 tails 数组末尾。
返回 dp 数组：dp[i] 表示在每个位置的最长有效障碍物路线长度，最终返回 dp 数组。

C++代码

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        vector<int> tails;  // tails用于存储递增序列的末尾值
        vector<int> dp;     // dp用于存储结果

        for (int obstacle : obstacles) {
            // 使用lower_bound找到第一个大于当前障碍物的元素位置
            int pos = upper_bound(tails.begin(), tails.end(), obstacle) - tails.begin();
            
            if (pos < tails.size()) {
                tails[pos] = obstacle;  // 替换该位置的值
            } else {
                tails.push_back(obstacle);  // 如果没有合适的位置，追加当前障碍物
            }
            
            dp.push_back(pos + 1);  // dp[i]表示在第i个位置的最长有效路线长度
        }
        
        return dp;
    }
};

C++代码解释总结：

二分查找：通过 upper_bound 找到 tails 数组中第一个大于当前 obstacle 的位置。
更新 tails 数组：如果找到位置 pos，则更新该位置的值；否则将当前 obstacle 追加到 tails 数组末尾。
返回 dp 数组：dp[i] 表示在每个位置的最长有效障碍物路线长度，最终返回结果。

总结

核心思想：最长有效障碍物路线问题通过将障碍物的高度序列转化为 最长递增子序列（LIS） 的变种问题，可以通过动态规划和二分查找来高效求解。
时间复杂度：通过使用二分查找维护 tails 数组，时间复杂度为 O(n log n)，适合处理大规模数据。
解决方案：本文详细介绍了 Python 和 C++ 实现，展示了如何通过二分查找和动态规划来高效地找到每个位置的最长有效障碍物路线长度。

Albert_Lsk