leetcode 300
2021/11/22 6:10:11
本文主要是介绍leetcode 300,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
子数组指数组中去掉一些元素(也可以不去)并且不改变剩下元素的顺序后产生的数组. 递增子数组指满足元素为递增的子数组. 给到一个数组, 求得最长的递增子数组的长度.
要求复杂度为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)
这篇关于leetcode 300的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc