本文主要是介绍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
- https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
这篇关于Leetcode 1964. Find the Longest Valid Obstacle Course at Each Position的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!