文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書(shū)

1. Description

Find the Longest Valid Obstacle Course at Each Position

2. Solution

解析：Version 1，這道題跟Leetcode 300很像，可以構(gòu)造一個(gè)最長(zhǎng)非遞減子序列，使用order作為有序序列保持最長(zhǎng)非遞減子序列長(zhǎng)度，當(dāng)新元素大于或等于有序序列的最后一個(gè)元素時(shí)，此時(shí)增加新元素到有序序列中，否則，則將新元素插入到當(dāng)前序列中，替換比其大的元素，保證左側(cè)元素都比它小，此時(shí)長(zhǎng)度不變，order中相同序列位置上始終保留較小的元素，這樣利于插入新元素。插入新元素時(shí)，結(jié)果就是序列長(zhǎng)度，更新元素時(shí)，長(zhǎng)度為索引位值加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] = obstacle
                result.append(index+1)
        return result

Reference

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