最長連續遞增子數組 求O(n)解法

wisdompeak2 发表于 2021-02-26 23:55:29
原题问的其实是最长的连续subsequence，不是最长的连续subarray。你看一下它的示例就知道了。所以你的代码其实不对。

没注意看样例。直接看到子数组就以为是subarray了。

lc上有吧，忘了题号了

维护一个数组dp和一个哈希表map_，哈希表记录nums[i]最后出现位置，如果nuns[i]-1出现过，dp[i]=dp[map_[nums[i]-1]+1，否则等于1，这样可以实现一次扫描

这样做可以吗？
我试了试你给的输入，结果是对的，但是没有跑其他的test

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <unordered_map>
   
5. using namespace std;
   
6. int longestInc(vector<int>& nums)
   
7. {
   
8.     unordered_map<int,int> m;
   
9.     int res = 1;
   
10.     for(int i : nums)
    
11.     {
    
12.         if(m.count(i-1)) m[i]=m[i-1]+1;
    
13.         else m[i]=1;
    
14.         res = max(res, m[i]);
    
15.     }
    
16.     return res;
    
17. }
    
18. int main()
    
19. {
    
20.     vector<int> nums{14,15,8,6,9,10,7,1,3,11,20,12};
    
21.     cout<<longestInc(nums);
    
22. 
    
23.     return 0;
    
24. [/i][/i][/i][i][i][i]}[/i][/i][/i]
    
25. [i][i][i]

复制代码

[/i][/i][/i]

Leetcode 128?

1. sort之后双指针 Ologn
2. union find with path compression On
3. dp with a hashmap to record index of an element
On

ansjcy 发表于 2021-03-03 01:45:27
1. sort之后双指针 Ologn
2. union find with path compression On
3. dp with a hashmap to record index of an

typo：sort之后双指针：Onlogn