专栏：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)笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴