精品推薦 ： 《征服資料結構》 專欄 ：50多種資料結構徹底征服 《經典圖論算法》 專欄 ：50多種經典圖論算法全部掌握 一程式員因為腦癱，肢體動作略顯僵硬，問要不要寫在履歷上。 有的網友建議寫上，有的建議不要寫， 其實這種如果不影響工作的話可寫也可不寫。 不過我覺得最好寫上，并且注明一下不會影響到工作。因為不寫的話，面試的時候如果公司嫌棄，它會以各種理由拒絕，面試白跑一趟，也挺難受的。 --------------下面是今天的算法題-------------- 來看下今天的算法題，這題是LeetCode的第300題：最長遞增子序列。 問題描述 來源：LeetCode第300題 難度：中等 給你一個整數數組 nums ，找到其中 最長嚴格遞增子序列的長度 。 子序列是由數組派生而來的序列，删除（或不删除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [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 = [7,7,7,7,7,7,7] 輸出 ：1 1 <= nums.length <= 2500 -10^4 <= nums[i] <= 10^4 問題分析 這題我們昨天剛講過 《 最長遞增子序列 》 ，使用的是動态規劃的解決方式，這裡我們使用二分查找的方式再來解這題。 我們把計算的最長遞增子序列儲存到集合list中，如果目前元素大于集合的最後一個元素，說明目前元素可以和集合構成一個更長的遞增子序列，我們就把目前元素添加到集合中。 比如集合中的元素：[1,3,4,6]，目前元素是 8 ，如果把 8 添加到集合中就會構成更長的集合[1,3,4,6,8]。 如果目前元素小于集合的最後一個元素，為了保證 集合中的元素盡可能小 ，我們可以讓目前元素替換集合中第一個大于它的元素。 比如集合中的元素：[1,3,5,6]，目前元素是 4 ，我們可以讓 4 替換 5 ，變成 [1,3,4,6]，因為 集合中的元素越小，構成最長遞增子序列的機會就越大 。 因為集合中的元素都是有序的，是以替換隻需要進行二分查找即可。 JAVA： public int lengthOfLIS(int[] nums) { // mList中儲存的是構成的上升子序列 List mList = new ArrayList<>(nums.length); for (int num : nums) { // 添加到集合的最後 if (mList.size() == 0 || mList.get(mList.size() - 1) < num) mList.add(num); else { // 二分查找 int i = Collections.binarySearch(mList, num); // 替換，這裡要注意，如果查找到，i 會傳回查找元素的下标，如果沒 // 找到，就會傳回它應該存放的位置，然後取反，是以是個負數。 mList.set((i < 0) ? -i - 1 : i, num); } } return mList.size();} C++： public: int lengthOfLIS(vector &nums) { vector mList; mList.reserve(nums.size()); for (int num: nums) { if (mList.empty() || mList.back() < num) { mList.push_back(num); } else { // 二分查找 auto it = lower_bound(mList.begin(), mList.end(), num); *it = num; } } return mList.size(); } Python： def lengthOfLIS(self, nums: List[int]) -> int: mList = [] for num in nums: if not mList or mList[-1] < num: mList.append(num) else: # 二分查找 i = bisect_left(mList, num) mList[i] = num return len(mList) 筆者簡介 博哥，真名： 王一博 ，畢業十多年， 《算法秘籍》 作者，專注于 資料結構和算法 下載下傳我整理的1000多頁的PDF算法文檔 。 《征服資料結構》專欄 數組 ， 稀疏表(Sparse Table) ， 單向連結清單 ， 雙向連結清單 ， 塊狀連結清單 ， 跳表 ， 隊列和循環隊列 ， 雙端隊列 ， 單調隊列 ， 棧 ， 單調棧 ， 雙端棧 ， 散清單 ， 堆 ， 字典樹(Trie樹) ， ArrayMap ， SparseArray ， 二叉樹 ， 二叉搜尋樹(BST) ， 笛卡爾樹 ， AVL樹 ， 樹堆(Treap) ， FHQ-Treap …… 《經典圖論算法》專欄 圖的介紹 ， 圖的表示方式 ， 鄰接矩陣轉換 ， 廣度優先搜尋(BFS) ， 深度優先搜尋(DFS) ， A*搜尋算法 ， 疊代深化深度優先搜尋(IDDFS) ， IDA*算法 ， 雙向廣度優先搜尋 ， 迪傑斯特拉算法(Dijkstra) ， 貝爾曼-福特算法(Bellman-Ford) ， SPFA算法 ， 弗洛伊德算法(Floyd) ……