刷leetcode——力扣300——最長上升子序列

這道題主要涉及動態規劃，優化時可以考慮貪心算法和二分查找。

原題

給定一個無序的整數數組，找到其中最長上升子序列的長度。

示例:

<code>輸入: [10,9,2,5,3,7,101,18]輸出: 4 解釋: 最長的上升子序列是[2,3,7,101]，它的長度是 4。/<code>

說明:

• 可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
• 你算法的時間複雜度應該為 O(n2) 。

進階: 你能將算法的時間複雜度降低到 O(n log n) 嗎?

解題

暴力法

這也是最基礎的想法，利用遞歸，從每一個數開始，一個一個尋找，只要比選中的標準大，那麼就以新的數為起點，繼續找。全部找完後，找出最長的序列即可。

也看一下代碼：

<code>class Solution {    public int lengthOfLIS(int[] nums) {        // 遞歸查詢        return recursiveSearch(nums, Integer.MIN_VALUE, 0);    }    public int recursiveSearch(int[] nums, int standard, int index) {        if (nums.length == index) {            return 0;        }                // 如果包含當前index的數字，其遞增長度        int tokenLength = 0;        if (nums[index] > standard) {            tokenLength = 1 + recursiveSearch(nums, nums[index], index + 1);        }        // 如果不包含當前index的數字，其遞增長度        int notTokenLength = recursiveSearch(nums, standard, index + 1);        // 返回較大的那個值        return tokenLength > notTokenLength ? tokenLength : notTokenLength;    }}/<code> 

提交之後報超出時間限制，這個也是預料到的，那麼我們優化一下。

記錄中間結果

仔細分析一下上面的暴力解法，假設 nums 是： [10,9,2,5,3,7,101,18]，那麼從 7 到 101 這個查找，在2、5、3的時候，都曾經查找過一遍。

那麼針對這種重複查找的情況，我們可以用一個二維數組，記錄一下中間結果，這樣就可以達到優化的效果。比如用int[][] result標記為記錄中間結果的數組，那麼result[i][j]就代表著從 nums[i - 1] 開始，無論包含還是不包含 nums[j] 的最大遞增序列長度。這樣就能保證不再出現重複計算的情況了。

讓我們看看代碼：

<code>class Solution {    public int lengthOfLIS(int[] nums) {        // 記錄已經計算過的結果        int result[][] = new int[nums.length + 1][nums.length];        for (int i = 0; i < nums.length + 1; i++) {            for (int j = 0; j < nums.length; j++) {                result[i][j] = -1;            }        }        // 遞歸查詢        return recursiveSearch(nums, -1, 0, result);    }    public int recursiveSearch(int[] nums, int preIndex, int index, int[][] result) {        if (nums.length == index) {            return 0;        }        // 如果已經賦值，說明計算過，因此直接返回        if (result[preIndex + 1][index] > -1) {            return result[preIndex + 1][index];        }        // 如果包含當前index的數字，其遞增序列最大長度        int tokenLength = 0;        if (preIndex < 0 || nums[index] > nums[preIndex]) {            tokenLength = 1 + recursiveSearch(nums, index, index + 1, result);        }        // 如果不包含當前index的數字，其遞增序列最大長度        int notTokenLength = recursiveSearch(nums, preIndex, index + 1, result);        // 返回較大的那個值        result[preIndex + 1][index] = tokenLength > notTokenLength ? tokenLength : notTokenLength;        return result[preIndex + 1][index];    }}/<code>

提交OK，但是結果感人，幾乎是最慢的了，無論時間還是空間上，都只打敗了5%左右的用戶，那就繼續優化。

<code>    ### 動態規劃/<code>

假設我知道了從 nums[0] 到 nums[i] 的最大遞增序列長度，那麼針對 nums[i + 1]，我只要去跟前面的所有數比較一下，找出前面所有數中比 nums[i + 1] 小的數字中最大的遞增子序列，再加1就是 nums[i + 1] 對應的最大遞增子序列。

這樣我只要再記錄一個最大值，就可以求出整個數組的最大遞增序列了。

讓我們看看代碼：

<code>class Solution {    public int lengthOfLIS(int[] nums) {        if (nums.length == 0) {            return 0;        }        // 動態規劃，之前幾個數字中，有幾個比當前數小的，不斷更新        // 存儲中間結果        int[] dp = new int[nums.length];        // 最大值，因為數組中至少有一個，所以最小是1        int max = 1;                // 遍歷        for (int i = 0; i < dp.length; i++) {            // 當前下標i的最大遞增序列長度            int currentMax = 0;            for (int j = 0; j < i; j++) {                // 如果nums[i]比nums[j]大，那麼nums[i]可以加在nums[j]後面，繼續構成一個遞增序列                if (nums[i] > nums[j]) {                    currentMax = Math.max(currentMax, dp[j]);                }            }            // 加上當前的數            dp[i] = currentMax + 1;            max = Math.max(dp[i], max);        }        return max;    }}/<code>

提交OK，執行用時：9 ms，只戰勝了75.15%的 java 提交，看來還是可以繼續優化的。

貪心算法 + 二分查找

貪心算法意味著不需要是最完美的結果，只要針對當前是有效的，就可以了。

我們之前在構造遞增序列的時候，其實是在不斷根據之前的值進行更新的，並且十分準確。但其實並不需要如此，只要保證序列中每個數都相對較小，就可以得出最終的最大長度。

還是以 [10,9,2,5,3,7,101,18,4,8,6,12]舉例：

1. 從10到2，都是無法構成的，因為每一個都比之前的小。
2. 當以最小的2作為起點後，2,5、2,3都是可以作為遞增序列，但明顯感覺2,3更合適，因為3更小。
3. 因為7大於3，因此遞增序列增長為2,3,7。
4. 因為101也大於7，因此遞增序列增長為2,3,7,101。
5. 因為18小於101，但是大於7，因此我們可以用18替換101，因為18更小，序列更新為2,3,7,18
6. 此時遇到4，4大於3但是小於7，我們可以用它替換7，雖然此時新的序列2,3,4,18並不是真正的結果，但首先長度上沒有問題，其次如果出現新的可以排在最後的數，一定是大於4的，因為要先大於現在的最大值18。序列更新為2,3,4,18。
7. 同理，8大於4小於18，替換18，此時新的序列2,3,4,8，這樣是不是大家開始懂得了這個規律。
8. 遇到6之後，更新為2,3,4,6。
9. 遇到12後，更新為2,3,4,6,12。

這樣也就求出了最終的結果。

結合一下題目說明裡提到的O(nlogn)，那麼就可以想到二分查找，運用到這裡也就是找到當前數合適的位置。

接下來讓我們看看代碼：

<code>class Solution {    public int lengthOfLIS(int[] nums) {        if (nums.length == 0) {            return 0;        }        // 貪心 + 二分查找        // 一個空數組，用來存儲最長遞增序列        int[] result = new int[nums.length];        result[0] = nums[0];        // 空數組的長度        int resultLength = 1;        // 遍歷        for (int i = 1; i < nums.length; i++) {            int num = nums[i];            // 如果num比當前最大數大，則直接加在末尾            if (num > result[resultLength - 1]) {                result[resultLength] = num;                resultLength++;                continue;            }            // 如果和最大數相等，直接跳過            if (num == result[resultLength - 1]) {                continue;            }            // num比最大值小，則找出其應該存在的位置            int shouldIndex = Arrays.binarySearch(result, 0, resultLength, num);            if (shouldIndex < 0) {                shouldIndex = -(shouldIndex + 1);            }            // 更新，此時雖然得出的result不一定是真正最後的結果，但首先其resultLength不會變，之後就算resultLength變大，也是相對正確的結果            // 這裡的更新，只是為了讓result數組中每個位置上的數，是一個相對小的數字            result[shouldIndex] = num;        }        return resultLength;    }}/<code>

提交OK，執行用時：2 ms，差不多了。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題目用動態規劃其實就已經能解決了，但為了優化，還需要用到貪心算法和二分查找。

有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。

https://death00.github.io/

閱讀更多 健程之道 的文章

關鍵字: 算法 最長 序列