1964. Find the Longest Valid Obstacle Course at Each Position

题目信息

题号:

1964

难度:

Hard

主题:

最长非递减子序列、二分查找

原题:

LeetCode 1964

重点:

每个位置的答案必须使用该位置作为子序列末尾

题目重述

对每个下标 i,返回从前缀中选择并以 obstacles[i] 结尾的最长非递减子序列长度。

自建示例

输入:obstacles = [1,2,3,2]
输出:[1,2,3,3]
解释:最后位置可使用子序列 [1,2,2]。
输入:obstacles = [3,2,1]
输出:[1,1,1]
解释:每个新元素都更小,只能单独作为结尾。