Leetcode 1964. Find the Longest Valid Obstacle Course at Each Position

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Find the Longest Valid Obstacle Course at Each Position

2. Solution

解析:Version 1,这道题跟Leetcode 300很像,可以构造一个最长非递减子序列,使用order作为有序序列保持最长非递减子序列长度,当新元素大于或等于有序序列的最后一个元素时,此时增加新元素到有序序列中,否则,则将新元素插入到当前序列中,替换比其大的元素,保证左侧元素都比它小,此时长度不变,order中相同序列位置上始终保留较小的元素,这样利于插入新元素。插入新元素时,结果就是序列长度,更新元素时,长度为索引位值加1

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
n = len(obstacles)
order = []
result = []
for i, obstacle in enumerate(obstacles):
if len(order) == 0 or order[-1] <= obstacle:
order.append(obstacle)
result.append(len(order))
else:
index = bisect.bisect_right(order, obstacle)
order[index] = obstacle
result.append(index+1)
return result

Reference

  1. https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
如果有收获,可以请我喝杯咖啡!