子数组指数组中去掉一些元素(也可以不去)并且不改变剩下元素的顺序后产生的数组. 递增子数组指满足元素为递增的子数组. 给到一个数组, 求得最长的递增子数组的长度.
要求复杂度为O(nlogn)
我想了好久没有想出来一个很好的办法, 后来抄别人答案有点搞懂了, 然后又自己写了一遍. 大概是懂了吧, 但是今晚太晚了, 以后再补上我的理解.
以上
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
longest_val_list = []
longest_index_list = []
lis_list = []
longest_val_list.append(nums[0])
longest_index_list.append(0)
lis_list.append(1)
for i in range(1, len(nums)):
val = nums[i]
if val > longest_val_list[-1]:
longest_val_list.append(val)
longest_index_list.append(i)
lis_list.append(len(longest_val_list))
continue
start = 0
end = len(longest_val_list) - 1
while start < end:
mid = (start + end) // 2
if longest_val_list[mid] >= val:
end = mid
else:
start = mid + 1
longest_val_list[start] = val
# # can add or not add
# longest_index_list[start] = i
lis_list.append(start + 1)
# print(lis_list)
# print(longest_val_list)
# print(longest_index_list)
return max(lis_list)