leecode 300. Longest Increasing Subsequence
发布时间:2020-12-14 03:23:33 所属栏目:大数据 来源:网络整理
导读:Given an unsorted array of integers,find the length of longest increasing subsequence. Example: Input: Output: 4 Explanation: The longest increasing subsequence is,therefore the length is . [10,9,2,5,3,7,101,18][2,101]4 Note: There may be
Given an unsorted array of integers,find the length of longest increasing subsequence. Example: Input: Output: 4 Explanation: The longest increasing subsequence is,therefore the length is . [10,9,2,5,3,7,101,18][2,101]4 Note:
Follow up:?Could you improve it to O(n?log?n) time complexity? ? 题目大意:找出无序数组中最长上升子序列的长度, 时间复杂度要求为O(nlgn); 最直接的办法是暴力求解,记录下每个位置的上升序列长度, 当要计算某个位置的上升序列长度的时候,就向前面找到比该值小且上升序列的长度和该位置的上升序列长度差值不超过一的数; 这样做的方法简单,但是会进行很多重复的查询; 改进办法:用一个数组来模拟栈lis,这个数组按照记录出现的升序数字, 当新出现的数字比栈顶的数字大, 则添加到栈中,否则更新数组中的数;?? Input: 1 class Solution { 2 public: 3 int lengthOfLIS(vector<int>& nums) { 4 if(nums.size()==0) return 0; 5 auto m=nums.begin(); 6 for(auto num:nums){ 7 auto it=lower_bound(nums.begin(),m,num); 8 *it=num; 9 if(it==m) m++; 10 } 11 return m-nums.begin(); 12 } 13 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |