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

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

1. Description

2. Solution

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

• Version 1

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] = obstacleresult.append(index+1)return result

Reference

1. https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/