穿上衣服我就不認識你了？來聊聊最長上升子序列 · ttttt

# 穿上衣服我就不認識你了？來聊聊最長上升子序列 # 穿上衣服我就不認識你了？來聊聊最長上升子序列最長上升子序列是一個很經典的算法題。有的會直接讓你求最長上升子序列，有的則會換個說法，但最終考察的還是最長上升子序列。那么問題來了，它穿上衣服你還看得出來是么？如果你完全看不出來了，說明抽象思維還不到火候。經常看我的題解的同學應該會知道，我經常強調`抽象思維`。沒有抽象思維，所有的題目對你來說都是新題。你無法將之前做題的經驗遷移到這道題，那你做的題意義何在？雖然抽象思維很難練成，但是幸好算法套路是有限的，經常考察的題型更是有限的。從這些入手，或許可以讓你輕松一些。本文就從一個經典到不行的題型《最長上升子序列》，來幫你進一步理解`抽象思維`。 > 注意。本文是幫助你識別套路，從橫向上理清解題的思維框架，并沒有采用最優解，所有的題目給的解法都不是最優的，但是都可以通過所有的測試用例。如果你想看最優解，可以直接去討論區看。或者期待我的`深入剖析系列`。 ## 300. 最長上升子序列 ### 題目地址 <https://leetcode-cn.com/problems/longest-increasing-subsequence> ### 題目描述 ``` <pre class="calibre18">``` 給定一個無序的整數數組，找到其中最長上升子序列的長度。示例: 輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。說明: 可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。你算法的時間復雜度應該為 O(n2) 。進階: 你能將算法的時間復雜度降低到 O(n log n) 嗎? ``` ``` ### 思路 > 美團和華為都考了這個題。題目的意思是讓我們從給定數組中挑選若干數字，這些數字滿足： `如果 i < j 則 nums[i] < nums[j]`。問：一次可以挑選最多滿足條件的數字是多少個。 ![](https://img.kancloud.cn/6d/18/6d188332e5cd4882c026cacc931e0196_1586x514.jpg) 這種子序列求極值的題目，應該要考慮到貪心或者動態規劃。這道題貪心是不可以的，我們考慮動態規劃。按照動態規劃定義狀態的套路，我們有**兩種常見**的定義狀態的方式： - dp\[i\] : 以 i 結尾（一定包括 i）所能形成的最長上升子序列長度, 答案是 max(dp\[i\])，其中 i = 0,1,2, ..., n - 1 - dp\[i\] : 以 i 結尾（可能包括 i）所能形成的最長上升子序列長度，答案是 dp\[-1\] （-1 表示最后一個元素）容易看出第二種定義方式由于無需比較不同的 dp\[i\] 就可以獲得答案，因此更加方便。但是想了下，狀態轉移方程會很不好寫，因為 dp\[i\] 的末尾數字（最大的）可能是任意 j < i 的位置。第一種定義方式雖然需要比較不同的 dp\[i\] 從而獲得結果，但是我們可以在循環的時候順便得出，對復雜度不會有影響，只是代碼多了一點而已。因此我們**選擇第一種建模方式**。 ![](https://img.kancloud.cn/66/09/6609d8a6b6be13a5e0ae671807fc1819_1586x339.jpg) 由于 dp\[j\] 中一定會包括 j，且以 j 結尾，那么 nums\[j\] 一定是其所形成的序列中最大的元素，那么如果位于其后（意味著 i > j）的 nums\[i\] > nums\[j\]，那么 nums\[i\] 一定能夠融入 dp\[j\] 從而形成更大的序列，這個序列的長度是 dp\[j\] + 1。因此狀態轉移方程就有了：`dp[i] = dp[j] + 1 (其中 i > j, nums[i] > nums[j])` 以 `[10, 9, 2, 5, 3, 7, 101, 18]` 為例，當我們計算到 dp\[5\]的時候，我們需要往回和 0，1，2，3，4 進行比較。 ![](https://img.kancloud.cn/1c/30/1c306f175122fa88b9c548e556c0b819_1350x872.jpg) 具體的比較內容是： ![](https://img.kancloud.cn/18/e2/18e2b49801f80b13eeded4fb5d39223c_1102x572.jpg) 最后從三個中選一個最大的 + 1 賦給 dp\[5\]即可。 ![](https://img.kancloud.cn/9d/93/9d93bf53057ed392f6fb33167f9f6912_1252x196.jpg) **記住這個狀態轉移方程，后面我們還會頻繁用到。** ### 代碼 ``` <pre class="calibre18">``` class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 dp = [1] * n ans = 1 for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) ans = max(ans, dp[i]) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(N)O(N)O(N) ## 435. 無重疊區間 ### 題目地址 <https://leetcode-cn.com/problems/non-overlapping-intervals/> ### 題目描述 ``` <pre class="calibre18">``` 給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊。注意: 可以認為區間的終點總是大于它的起點。區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。示例 1: 輸入: [ [1,2], [2,3], [3,4], [1,3] ] 輸出: 1 解釋: 移除 [1,3] 后，剩下的區間沒有重疊。示例 2: 輸入: [ [1,2], [1,2], [1,2] ] 輸出: 2 解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。示例 3: 輸入: [ [1,2], [2,3] ] 輸出: 0 解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。 ``` ``` ### 思路我們先來看下最終**剩下**的區間。由于剩下的區間都是不重疊的，因此剩下的**相鄰區間的后一個區間的開始時間一定是不小于前一個區間的結束時間的**。比如我們剩下的區間是`[ [1,2], [2,3], [3,4] ]`。就是第一個區間的 2 小于等于第二個區間的 2，第二個區間的 3 小于等于第三個區間的 3。不難發現如果我們將`前面區間的結束`和`后面區間的開始`結合起來看，其就是一個**非嚴格遞增序列**。而我們的目標就是刪除若干區間，從而**剩下最長的非嚴格遞增子序列**。這不就是上面的題么？只不過上面是嚴格遞增，這不重要，就是改個符號的事情。上面的題你可以看成是刪除了若干數字，然后剩下**剩下最長的嚴格遞增子序列**。 **這就是抽象的力量，這就是套路。** 如果對區間按照起點或者終點進行排序，那么就轉化為上面的最長遞增子序列問題了。和上面問題不同的是，由于是一個區間。因此實際上，我們是需要拿**后面的開始時間**和**前面的結束時間**進行比較。 ![](https://img.kancloud.cn/ff/2b/ff2b5fa520390de2a06df69e32303774_1296x362.jpg) 而由于： - 題目求的是需要移除的區間，因此最后 return 的時候需要做一個轉化。 - 題目不是要求嚴格遞增，而是可以相等，因此我們的判斷條件要加上等號。 > 這道題還有一種貪心的解法，其效率要比動態規劃更好，但由于和本文的主題不一致，就不在這里講了。 ### 代碼 **你看代碼多像** ``` <pre class="calibre18">``` class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) if n == 0: return 0 dp = [1] * n ans = 1 intervals.sort(key=lambda a: a[1]) for i in range(len(intervals)): for j in range(i - 1, -1, -1): if intervals[i][0] >= intervals[j][1]: dp[i] = max(dp[i], dp[j] + 1) # 由于我事先進行了排序，因此倒著找的時候，找到的第一個一定是最大的數，因此不用往前繼續找了。 # 這也是為什么我按照結束時間排序的原因。 break dp[i] = max(dp[i], dp[i - 1]) ans = max(ans, dp[i]) return n - ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(N)O(N)O(N) ## 646. 最長數對鏈 ### 題目地址 <https://leetcode-cn.com/problems/maximum-length-of-pair-chain/> ### 題目描述 ``` <pre class="calibre18">``` 給出 n 個數對。在每一個數對中，第一個數字總是比第二個數字小。現在，我們定義一種跟隨關系，當且僅當 b < c 時，數對(c, d) 才可以跟在 (a, b) 后面。我們用這種形式來構造一個數對鏈。給定一個對數集合，找出能夠形成的最長數對鏈的長度。你不需要用到所有的數對，你可以以任何順序選擇其中的一些數對來構造。示例 : 輸入: [[1,2], [2,3], [3,4]] 輸出: 2 解釋: 最長的數對鏈是 [1,2] -> [3,4] 注意：給出數對的個數在 [1, 1000] 范圍內。 ``` ``` ### 思路和上面的`435. 無重疊區間`是換皮題，唯一的區別這里又變成了嚴格增加。沒關系，我們把等號去掉就行了。并且由于這道題求解的是最長的長度，因此轉化也不需要了。 > 當然，這道題也有一種貪心的解法，其效率要比動態規劃更好，但由于和本文的主題不一致，就不在這里講了。 ### 代碼 **這代碼更像了！** ``` <pre class="calibre18">``` class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: n = len(pairs) dp = [1] * n ans = 1 pairs.sort(key=lambda a: a[0]) for i in range(n): for j in range(i): if pairs[i][0] > pairs[j][1]: dp[i] = max(dp[i], dp[j] + 1) ans = max(ans, dp[i]) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(N)O(N)O(N) ## 452. 用最少數量的箭引爆氣球 ### 題目地址 <https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/> ### 題目描述 ``` <pre class="calibre18">``` 在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。由于它是水平的，所以y坐標并不重要，因此只要知道開始和結束的x坐標就足夠了。開始坐標總是小于結束坐標。平面內最多存在104個氣球。一支弓箭可以沿著x軸從不同點完全垂直地射出。在坐標x處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend，且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。 Example: 輸入: [[10,16], [2,8], [1,6], [7,12]] 輸出: 2 解釋: 對于該樣例，我們可以在x = 6（射爆[2,8],[1,6]兩個氣球）和 x = 11（射爆另外兩個氣球）。 ``` ``` ### 思路把氣球看成區間，幾個箭可以全部射爆，意思就是有多少不重疊的區間。注意這里重疊的情況也可以射爆。這么一抽象，就和上面的`646. 最長數對鏈`一模一樣了，不用我多說了吧？ > 當然，這道題也有一種貪心的解法，其效率要比動態規劃更好，但由于和本文的主題不一致，就不在這里講了。 ### 代碼 **代碼像不像？** ``` <pre class="calibre18">``` class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: n = len(points) if n == 0: return 0 dp = [1] * n cnt = 1 points.sort(key=lambda a:a[1]) for i in range(n): for j in range(0, i): if points[i][0] > points[j][1]: dp[i] = max(dp[i], dp[j] + 1) cnt = max(cnt, dp[i]) return cnt ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(N)O(N)O(N) ## More 其他的我就不一一說了。比如 [673. 最長遞增子序列的個數](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/) （滴滴面試題）。不就是求出最長序列，之后再循環比對一次就可以得出答案了么？ [491. 遞增子序列](https://leetcode-cn.com/problems/increasing-subsequences/) 由于需要找到所有的遞增子序列，因此動態規劃就不行了，妥妥回溯就行了，套一個模板就出來了。回溯的模板可以看我之前寫的[回溯專題](https://github.com/azl397985856/leetcode/blob/master/problems/90.subsets-ii.md "回溯專題")。大家把我講的思路搞懂，這幾個題一寫，還怕碰到類似的題不會么？**只有熟練掌握基礎的數據結構與算法，才能對復雜問題迎刃有余。** 最長上升子序列就是一個非常經典的基礎算法，把它徹底搞懂，再去面對出題人的各種換皮就不怕了。相反，如果你不去思考題目背后的邏輯，就會刷地很痛苦。題目稍微一變化你就不會了，這也是為什么很多人說**刷了很多題，但是碰到新的題目還是不會做**的原因之一。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)