一、題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。

子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

?
示例 1：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]
輸出：1
?

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104
?

進(jìn)階：

你能將算法的時(shí)間復(fù)雜度降低到?O(n log(n)) 嗎?

二、思路講解

? ? ? ? 用dp[i] 表示以i 結(jié)尾的序列中，最大遞增子序列的長度。那么我們在每個(gè)i 處，往前找比自己小的數(shù)字（記為j 處），將該處的dp值+1，即是i處的dp值（說明i處的數(shù)字可以接在j 處后面組成遞增子序列）。dp數(shù)組中的最大值即為所求。

三、Java代碼實(shí)現(xiàn)

class Solution {
    public int lengthOfLIS(int[] nums) {

        //數(shù)組長度
        int len = nums.length;
        //最后結(jié)果
        int res = 0;
        //dp[i]表示以i結(jié)尾的序列的最大遞增子序列長度
        int []dp = new int[len];
        //給dp賦初值
        for(int i=0; i<len; i++) {
            dp[i] = 1;
        }

        for(int i=0; i<len; i++) {
            int big = 0;
            for(int j=0; j<i; j++) {
                if(nums[j]<nums[i]) {
                    big = Math.max(big, dp[j]);
                }
            }
            dp[i] = big + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

? ? ? ? 時(shí)間復(fù)雜度：? ? ? ? O(N^2)

? ? ? ? 空間復(fù)雜度：? ? ? ? O(N)?

四、算法優(yōu)化

? ? ? ? 進(jìn)階要求是要時(shí)間復(fù)雜度為nlogn。我們的算法的時(shí)間復(fù)雜度主要為：遍歷nums數(shù)組，使用n，無法優(yōu)化；線性遍歷[0, i-1) 求dp[i]，使用n。我們可以考慮重新設(shè)計(jì)dp的思路。

? ? ? ? 設(shè)計(jì)一個(gè)tail數(shù)組，tail[i] 表示長度為i的遞增序列的最小末尾數(shù)字。例如，4 5 1 9 8 5 序列中，長度為1的遞增序列有4，5，1，9，8，5，所以tail[1]為1；長度為1的遞增序列有4 5，4 9，4 8，

5 8， 5 9……所以tail[2] 為5；長度為3的遞增序列有 4 5 9，4 5?8，所以tail[3] 為8?？梢钥闯?，tail為一個(gè)遞增序列，在查找操作時(shí)，我們可以使用二分查找。

? ? ? ? 那么，我們在計(jì)算tail[i]的時(shí)候，只需要遍歷nums，找到第一個(gè)比num大的tail[k]，說明num更適合放在tail[k-1]位置，而不能接在tail[k]位置（接上就不遞增了）。如果num比tail中所有數(shù)字都大，那就說明num適合接在所有遞增序列之后，這時(shí)遞增序列的長度又可以增加了。

? ? ? ? 參考：力扣300. 最長遞增子序列（動態(tài)規(guī)劃 + 二分查找，清晰圖解）

class Solution {
    public int lengthOfLIS(int[] nums) {

        //數(shù)組長度
        int len = nums.length;
        //tail[i]表示，長度為i的遞增序列的最小末尾數(shù)字
        int []tail = new int[len];

        //題目所求 遞增序列的最大長度
        int resLen = 0;
        for(int i=0; i<len; i++) {
            int left = 0;
            int right = resLen;
            //二分查找 找到比nums[i]大的tail，若找不到，說明nums[i]適合放在所有序列的末尾，那么就向后更新一個(gè)長度
            while(left < right) {
                int mid = (left+right) / 2;
                if(tail[mid]<nums[i]) {
                    left = mid+1;
                } else {
                    right = mid;
                }
            }
            tail[left] = nums[i];
            //更新長度
            resLen = resLen==right? (resLen+1) : resLen;
        }
        return resLen;
    }
}

? ? ? ? 時(shí)間復(fù)雜度：? ? ? ? O(NlogN)

? ? ? ? 空間復(fù)雜度：? ? ? ? O(N)文章來源地址http://www.zghlxwxcb.cn/news/detail-660819.html

到了這里，關(guān)于力扣300：最長遞增子序列（Java動態(tài)規(guī)劃+雙指針）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！