300 最长上升子序列
最简单的做法就是动态规划，每个元素维护一个dp值，代表了以它为结尾的最长上升子序列长度（至少为1）。每扫描到一个新的元素时，都从前面所有元素中，选择小于当前元素且dp值最大的元素作为上升子序列的前一个元素。
时间复杂度：O(n^2)，空间复杂度：O(n)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for(int i = 0; i < nums.size(); i++){
dp.push_back(1);
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if(dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
}
}
}
int lis_len = 0;
for(int i = 0; i < dp.size(); i++){
if(dp[i] > lis_len)
lis_len = dp[i];
}
return lis_len;
}
};
上面的做法还是有些笨拙，贪心+二分查找是更好的做法。
对于每种长度的上升子序列，维护一个值，表示当前该长度的上升子序列的最小结尾元素，也就是min_ele数组。这是一种贪心的思想，尽可能减小上升子序列的结尾元素，后面就可以接入更多的数，使整个数组的上升子序列变得更长。
每扫描到一个新的元素时，将其与min_ele数组的最后一个元素比较，如果大于则上升子序列长度加1，当前元素接在min_ele数组最后；否则，用这个元素去更新已有的min_ele数组元素，利用二分查找，找到第一个不小于它的位置，替换进去。这样，就可以保证，min_ele数组是一个严格单调递增的数组。
class Solution {
public:
int bin_search(vector<int>& v, int ele){
int l = 0, r = v.size();
while(l < r){
int m = (l + r) >> 1;
if(v[m] < ele) l = m + 1;
else r = m;
}
return l;
}
int lengthOfLIS(vector<int>& nums) {
int cur_len = 0;
vector<int> min_ele;
for(int i = 0; i < nums.size(); i++){
if(cur_len == 0 || nums[i] > min_ele[cur_len - 1]){
min_ele.push_back(nums[i]);
cur_len++;
}
else{
int idx = bin_search(min_ele, nums[i]);
min_ele[idx] = nums[i];
}
}
return cur_len;
}
};
重要！！二分查找的说明
这里关于二分查找，我花了比较长时间来确保写对。真是一个使人进步的算法啊。
如果只是要求在数组nums中找到元素e，找到就返回e的下标，找不到就返回-1，是最简单的情况，这种情况其实很好写，每次比对nums[m]与e，相等就退出查找，否则缩小区间继续找，如果区间长度缩小为0还没有找到，那就返回-1.
但是，往往我们会遇到更多的要求，比如如果存在多个e，那么应该返回哪个；如果不存在e，应该返回-1还是返回最后一个不大于e的元素下标。
比如，返回最后一个不大于e的元素下标，那么，如果存在多个e，返回的就是最后一个下标；如果不存在e，返回的就是小于e的元素中最大的下标。区间边界设置为左闭右开，那么如下图所示，就要保证：
- lo左边的元素，一定是小于等于e的
- hi右边的元素，一定是大于e的
写出来的代码就应该是：
右边界左移的条件是：e<nums[m]，这样就可以保证hi右边的元素，一定是大于e的。
如果是另一种情况，要求返回第一个不小于e的元素下标，此时，如果存在多个e，返回第一个，不存在e，就返回第一个比e大的元素下标。需要保证：
- lo左边的元素，一定是小于e的
- hi右边的元素，一定是大于等于e的
这样，写出来的代码应该是：
int bin_search(vector<int>& nums, int e){
int lo = 0, hi = v.size();
while(lo < hi){
int m = (lo + hi) >> 1;
if(nums[m] < e) lo = m + 1;
else hi = m;
}
return lo;
}
右边界左移的条件是，e <= nums[m]，这样可以保证hi右边的元素，一定是大于等于e的。
当l=r时，循环退出，此时l左边的一定都是小于e的元素，右边的（包括l）一定是大于等于e的元素，我们就找到了一个分界点，返回这个分界点就可以。
上面最长上升子序列的问题，我返回的就是第二种情况，也就是第一个不小于e的元素的下标。
网友评论