1964. Find the Longest Valid Obstacle Course at Each Position
要你对 interger array 中的每个元素
找出以他为结尾的非严格递增 subsequence 最长长度是多少
Example 1:
Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.
Example 2:
Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.
Example 3:
Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.
思路:
1.可以想像一个画面是检查 obstacles[i] 时
前面已经有个 obstacles[0:i] 能组成的最长非严格递增 subsequence 叫他 arr 好了
然后就直接对 arr 二分搜就好 感觉就会直接是答案了
实作的方法就是维护这个 arr
obstacles[i] 有没有大于等于他最后一项 有的话就直接加在后面 没有就跳过
2.这方法假如遇到 [1,3,4,2,2,2] 就算不出正解了
因为检查到后面的 2 时 arr 会是 [1,3,4]
搜出来的 index 会一直都是 1 但其实后面的 2 有办法找到更长的 也就是 [1,2,2,2]
所以这里要尝试修改能把后面的 2 考虑进去
方法也很简单 就是 update arr[index] 成现在的数字
所以 [1,3,4,2]: arr = [1,3,4] -> [1,2,4]
[1,3,4,2,2]: arr = [1,2,4] -> [1,2,2]
[1,3,4,2,2,2]: arr = [1,2,2] -> [1,2,2,2]
也就是说 arr 的定义改变了 不是代表某个特定的 subsequence
变成 arr[i] 代表长度是 i 的 subsequence 中最后一项最小值可能是多少
因为 arr 还是维持非严格递增 所以检查 obstacles[i] 时二分搜搜到的结果
就是 arr 中小于等于 obstacles[i] 最靠右的那个 也就是长度最大的
Python code:
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) ->
List[int]:
arr = []
res = []
for num in obstacles:
if not arr or arr[-1] <= num:
arr.append(num)
res.append(len(arr))
else:
idx = bisect_right(arr, num)
arr[idx] = num
res.append(idx+1)
return res