class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
}
};
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.length1 <= n <= 1051 <= obstacles[i] <= 107原站题解
python3 解法, 执行用时: 200 ms, 内存消耗: 33.8 MB, 提交时间: 2023-09-27 10:22:12
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
python3 解法, 执行用时: 532 ms, 内存消耗: 33.5 MB, 提交时间: 2023-09-27 10:21:40
class Solution:
# 灵茶 题库
def longestObstacleCourseAtEachPosition(self, nums: List[int]) -> List[int]:
n = len(nums)
g = []
ans = []
for x in nums:
j = bisect_right(g, x)
if j == len(g):
g.append(x)
ans.append(len(g))
else:
g[j] = x
ans.append(len(g[:j+1]))
return ans
cpp 解法, 执行用时: 252 ms, 内存消耗: 120.7 MB, 提交时间: 2023-09-27 10:21:23
class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
int n = obstacles.size();
vector<int> ret;
vector<int> g;
for(int x : obstacles){
auto it = upper_bound(g.begin(), g.end(), x);
if(it == g.end()){
g.emplace_back(x);
ret.emplace_back(g.size());
} else {
*it = x;
ret.emplace_back(it - g.begin() + 1);
}
}
return ret;
}
};
golang 解法, 执行用时: 224 ms, 内存消耗: 9.8 MB, 提交时间: 2023-09-27 10:20:35
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
ans := make([]int, len(obstacles))
dp := []int{}
for i, v := range obstacles {
p := sort.SearchInts(dp, v+1) // 等价写法是二分不小于 v+1 的第一个位置
if p < len(dp) {
dp[p] = v
} else {
dp = append(dp, v)
}
ans[i] = p + 1
}
return ans
}