- Problem

1964. Find the Longest Valid Obstacle Course at Each Position

- 내 풀이

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        answer = [1]
        lis = [obstacles[0]]

        for num in obstacles[1:]:
            if num >= lis[-1]:
                lis.append(num)
                answer.append(len(lis))
            
            else:
                idx = bisect_right(lis, num)
                lis[idx] = num
                answer.append(idx + 1)
        
        return answer

- 결과

• 시간 복잡도: O(NlogN) (N = obstacles.length)
• 공간 복잡도: O(N)