[HOT 100] 1964. 找出到每个位置为止最长的有效障碍赛跑路线

1. 题目链接

1964. 找出到每个位置为止最长的有效障碍赛跑路线 - 力扣（LeetCode）

2. 题目描述

你打算构建一些障碍赛跑路线。给你一个 下标从 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 对应的最长障碍赛跑路线的长度

3. 题目示例

示例 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

4. 解题思路

1. 问题描述：给定一个整数数组obstacles，要求对于每个位置i，计算以obstacles[i]结尾的最长非递减子序列的长度。
2. 方法选择：本题可以使用动态规划和二分查找的结合方法。动态规划用于记录当前的最长非递减子序列，二分查找用于高效更新和维护这个序列。
3. 关键步骤：
   • 维护**dp**列表：dp列表用于存储当前的最长非递减子序列。对于每个元素v = obstacles[i]，在dp中找到第一个大于等于v + 1的位置p：
     • 如果p < dp.size()，说明可以替换dp[p]为v，以保持dp的非递减性。
     • 否则，将v添加到dp末尾，扩展最长非递减子序列。
   • 结果计算：以obstacles[i]结尾的最长非递减子序列的长度为p + 1，直接存入结果数组ans。
4. 二分查找优化：binarySearch函数使用二分查找在dp中找到第一个大于等于target的位置，时间复杂度为O(log k)（k为当前dp的长度）。
   
   

5. 题解代码

public class Solution {public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {// 初始化结果数组，ans[i]表示以obstacles[i]结尾的最长障碍子序列的长度int[] ans = new int[obstacles.length];// dp列表用于维护当前的最长递增子序列List<Integer> dp = new ArrayList<>();for (int i = 0; i < obstacles.length; i++) {int v = obstacles[i];// 在dp中找到第一个大于等于v+1的位置int p = binarySearch(dp, v + 1);if (p < dp.size()) {// 如果找到，用v替换该位置的元素dp.set(p, v);} else {// 否则将v添加到dp末尾dp.add(v);}// 当前最长障碍子序列的长度为p+1ans[i] = p + 1;}return ans;}// 二分查找：在list中找到第一个大于等于target的位置private int binarySearch(List<Integer> list, int target) {int left = 0;int right = list.size();while (left < right) {int mid = left + (right - left) / 2;if (list.get(mid) < target) {left = mid + 1;} else {right = mid;}}return left;}
}

6. 复杂度分析

1. 时间复杂度：
   • 遍历数组obstacles需要O(n)时间。
   • 对于每个元素，二分查找binarySearch需要O(log k)时间（k为当前dp的长度）。
   • 最坏情况下，dp的长度可能达到n，因此总时间复杂度为O(n log n)。
2. 空间复杂度：
   • dp列表最多存储n个元素，因此空间复杂度为O(n)。
   • 结果数组ans也需要O(n)空间。
   • 因此，总空间复杂度为O(n)。