這道題主要涉及動(dòng)態(tài)規(guī)劃，優(yōu)化時(shí)可以考慮貪心算法和二分查找。

原題

給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。

示例:

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

說明:

• 可能會(huì)有多種最長上升子序列的組合，你只需要輸出對(duì)應(yīng)的長度即可。
• 你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。

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

解題

暴力法

這也是最基礎(chǔ)的想法，利用遞歸，從每一個(gè)數(shù)開始，一個(gè)一個(gè)尋找，只要比選中的標(biāo)準(zhǔn)大，那么就以新的數(shù)為起點(diǎn)，繼續(xù)找。全部找完后，找出最長的序列即可。

也看一下代碼：

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; } // 如果包含當(dāng)前index的數(shù)字，其遞增長度 int tokenLength = 0; if (nums[index] > standard) { tokenLength = 1 + recursiveSearch(nums, nums[index], index + 1); } // 如果不包含當(dāng)前index的數(shù)字，其遞增長度 int notTokenLength = recursiveSearch(nums, standard, index + 1); // 返回較大的那個(gè)值 return tokenLength > notTokenLength ? tokenLength : notTokenLength; }}

提交之后報(bào)超出時(shí)間限制，這個(gè)也是預(yù)料到的，那么我們優(yōu)化一下。

記錄中間結(jié)果

仔細(xì)分析一下上面的暴力解法，假設(shè) nums 是： [10,9,2,5,3,7,101,18]，那么從 7 到 101 這個(gè)查找，在2、5、3的時(shí)候，都曾經(jīng)查找過一遍。

那么針對(duì)這種重復(fù)查找的情況，我們可以用一個(gè)二維數(shù)組，記錄一下中間結(jié)果，這樣就可以達(dá)到優(yōu)化的效果。比如用int[][] result標(biāo)記為記錄中間結(jié)果的數(shù)組，那么result[i][j]就代表著從 nums[i - 1] 開始，無論包含還是不包含 nums[j] 的最大遞增序列長度。這樣就能保證不再出現(xiàn)重復(fù)計(jì)算的情況了。

讓我們看看代碼：

class Solution { public int lengthOfLIS(int[] nums) { // 記錄已經(jīng)計(jì)算過的結(jié)果 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; } // 如果已經(jīng)賦值，說明計(jì)算過，因此直接返回 if (result[preIndex + 1][index] > -1) { return result[preIndex + 1][index]; } // 如果包含當(dāng)前index的數(shù)字，其遞增序列最大長度 int tokenLength = 0; if (preIndex < 0 || nums[index] > nums[preIndex]) { tokenLength = 1 + recursiveSearch(nums, index, index + 1, result); } // 如果不包含當(dāng)前index的數(shù)字，其遞增序列最大長度 int notTokenLength = recursiveSearch(nums, preIndex, index + 1, result); // 返回較大的那個(gè)值 result[preIndex + 1][index] = tokenLength > notTokenLength ? tokenLength : notTokenLength; return result[preIndex + 1][index]; }}

提交OK，但是結(jié)果感人，幾乎是最慢的了，無論時(shí)間還是空間上，都只打敗了5%左右的用戶，那就繼續(xù)優(yōu)化。

### 動(dòng)態(tài)規(guī)劃

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

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

讓我們看看代碼：

class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } // 動(dòng)態(tài)規(guī)劃，之前幾個(gè)數(shù)字中，有幾個(gè)比當(dāng)前數(shù)小的，不斷更新 // 存儲(chǔ)中間結(jié)果 int[] dp = new int[nums.length]; // 最大值，因?yàn)閿?shù)組中至少有一個(gè)，所以最小是1 int max = 1; // 遍歷 for (int i = 0; i < dp.length; i++) { // 當(dāng)前下標(biāo)i的最大遞增序列長度 int currentMax = 0; for (int j = 0; j < i; j++) { // 如果nums[i]比nums[j]大，那么nums[i]可以加在nums[j]后面，繼續(xù)構(gòu)成一個(gè)遞增序列 if (nums[i] > nums[j]) { currentMax = Math.max(currentMax, dp[j]); } } // 加上當(dāng)前的數(shù) dp[i] = currentMax + 1; max = Math.max(dp[i], max); } return max; }}

提交OK，執(zhí)行用時(shí)：9 ms，只戰(zhàn)勝了75.15%的 java 提交，看來還是可以繼續(xù)優(yōu)化的。

貪心算法 + 二分查找

貪心算法意味著不需要是最完美的結(jié)果，只要針對(duì)當(dāng)前是有效的，就可以了。

我們之前在構(gòu)造遞增序列的時(shí)候，其實(shí)是在不斷根據(jù)之前的值進(jìn)行更新的，并且十分準(zhǔn)確。但其實(shí)并不需要如此，只要保證序列中每個(gè)數(shù)都相對(duì)較小，就可以得出最終的最大長度。

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

從10到2，都是無法構(gòu)成的，因?yàn)槊恳粋€(gè)都比之前的小。

當(dāng)以最小的2作為起點(diǎn)后，2,5、2,3都是可以作為遞增序列，但明顯感覺2,3更合適，因?yàn)?更小。

因?yàn)?大于3，因此遞增序列增長為2,3,7。

因?yàn)?01也大于7，因此遞增序列增長為2,3,7,101。

因?yàn)?8小于101，但是大于7，因此我們可以用18替換101，因?yàn)?8更小，序列更新為2,3,7,18

此時(shí)遇到4，4大于3但是小于7，我們可以用它替換7，雖然此時(shí)新的序列2,3,4,18并不是真正的結(jié)果，但首先長度上沒有問題，其次如果出現(xiàn)新的可以排在最后的數(shù)，一定是大于4的，因?yàn)橐却笥诂F(xiàn)在的最大值18。序列更新為2,3,4,18。

同理，8大于4小于18，替換18，此時(shí)新的序列2,3,4,8，這樣是不是大家開始懂得了這個(gè)規(guī)律。

遇到6之后，更新為2,3,4,6。

遇到12后，更新為2,3,4,6,12。

這樣也就求出了最終的結(jié)果。

結(jié)合一下題目說明里提到的O(nlogn)，那么就可以想到二分查找，運(yùn)用到這里也就是找到當(dāng)前數(shù)合適的位置。

接下來讓我們看看代碼：

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

提交OK，執(zhí)行用時(shí)：2 ms，差不多了。

總結(jié)

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題目用動(dòng)態(tài)規(guī)劃其實(shí)就已經(jīng)能解決了，但為了優(yōu)化，還需要用到貪心算法和二分查找。

有興趣的話可以訪問我的博客或者關(guān)注我的公眾號(hào)、頭條號(hào)，說不定會(huì)有意外的驚喜。

https://death00.github.io/

公眾號(hào)：健程之道

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的找出最具竞争力的子序列_力扣300——最长上升子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。