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

給定一個亂序數組，數組裡的數皆不重複，求最長連續遞增子數組的長度（這題連續遞增的定義為：A[i1] = A[i2]−1 = A[i3]−2 = A[i4]−3 = ... = A[ik]−k+1）例：Ｓ＝ 14,15,8,6,9,10,7,1,3,11,20,12  輸出為：5 (S=[8,9,10,11,12])
想請問有沒有O(n)且不是動態規劃的解法

正解是建立一个hash表，hash[x]=i表示数值x所在的index。
我们扫一遍每个位置i，看j=hash[nums[i]-1]在哪里。如果存在且j位于i前面的话，那么以nums[i]为结尾最长连续subsequence的长度dp[i]就是dp[j]+1，否则就是dp[i]=1.
这是o(N)的DP解法。

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

不知道小帅 发表于 2021-2-25 14:17
[mw_shl_code=java,true]public int longestInc(int[] nums) {
    if (nums == null || nums.length == ...

原题问的其实是最长的连续subsequence，不是最长的连续subarray。你看一下它的示例就知道了。所以你的代码其实不对。

如果确定只是差1的话，双指针就可以到O(n)啊。或者贪心？反正就扫一遍就好了。给定i，然后往后找到最长的，和你的结果去一个max，然后直接从这个最长的结尾的下一个开始扫就好了。

不知道小帅 发表于 2021-2-25 13:36
如果确定只是差1的话，双指针就可以到O(n)啊。或者贪心？反正就扫一遍就好了。给定i，然后往后找到最长的， ...

不好意思，我看不太明白，可不可以再多解釋一點，想請問雙指針的話要怎麼寫？ 謝謝

AmberLNLF 发表于 2021-02-24 21:47:45
不好意思，我看不太明白，可不可以再多解釋一點，想請問雙指針的話要怎麼寫？ 謝謝

你用什么语言？我给你写一个代码出来好了。

不知道小帅 发表于 2021-2-25 14:11
你用什么语言？我给你写一个代码出来好了。

1. public int longestInc(int[] nums) {
   
2.     if (nums == null || nums.length == 0) return 0;
   
3.     int n = nums.length;
   
4.     int a = 0, ans  = 1;
   
5.     while (a < n) {
   
6.         int b = a;
   
7.         while (b + 1 < n && nums[b + 1] - nums[b]== 1) {
   
8.             ++b;
   
9.         }
   
10.         ans = Math.max(ans, b + 1 - a);
    
11.         a = b + 1;
    
12.     }
    
13.     return ans;}

复制代码

如果是java的话大概代码可以写成这样。

不知道小帅 发表于 2021-2-25 14:11
你用什么语言？我给你写一个代码出来好了。

Java, 如果可以的話 寫個Pseudocode就可以了
大大感謝你！！！  

不知道小帅 发表于 2021-2-25 14:17
[mw_shl_code=java,true]public int longestInc(int[] nums) {
    if (nums == null || nums.length == ...

謝謝你！！

AmberLNLF 发表于 2021-02-24 22:20:09
謝謝你！！

没事，你可以看一下，这样就是O(n) 的一个算法了。