动态规划—1964. 找出到每个位置为止最长的有效障碍赛跑路线
前言
最长有效障碍物路线问题 是一个涉及到 最长递增子序列（LIS） 变种的问题。给定一个障碍物高度的数组，要求在每个位置找到一个最长有效的障碍物路线，满足在该位置的障碍物高度必须大于或等于之前路线中的最大高度。这个问题结合了 动态规划 和 二分查找 的思想，我们可以使用这些算法来高效地求解该问题。
题目描述
基本思路
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] > obstacleif pos is valid:update tails[pos] with current obstacleelse:append obstacle to tailsset 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代码
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]表示在每个位置的最长有效障碍物路线长度，最终返回结果。
