目录

最长递增子序列

题解：

代码：

递增的三元子序列

题解：

代码：

简易版：

最长连续递增序列

题解：

代码： 

---

最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-increasing-subsequence/description/

题解：

如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

以数组 nums = [ 7, 3, 8, 4, 7, 2, 14, 13 ] 为例，从下标为 0 位置开始遍历：

当访问 nums[ 0 ] 时，此时长度为 1 的子序列的元素为 7；

当访问 nums[ 1 ] 时，由于 3 < 7，所以 7 和 3 无法构成递增子序列，所以长度为 1 的子序列的元素为 3 或者 7，此时长度为 1 的子序列的元素应该保留 3，去掉 7，原因如下：假如再来一个元素 x，

• 如果 x > 7，此时长度为 2 的子序列有两种可能，[ 3, x ] 或者 [ 7, x ] ；
• 如果 3 < x <= 7，那么长度为 2 的子序列只有 [ 3, x ] 一种情况。

也就是说，能与 7 构成递增子序列的元素，也一定可以与 3 构成递增子序列，但能与 3 构成递增子序列的元素不一定可以与 7 构成递增子序列，所以保留 3 去掉 7 可以让递增子序列的长度尽可能长！此时长度为 1 的子序列的最后一个元素为 3.

当访问 nums[ 2 ] 时，8 可以和 3 构成递增子序列，此时长度为 1 的子序列的最后一个元素为 3，长度为 2 的子序列的最后一个元素为 8.

当访问 nums[ 3 ] 时，4 比 8 小，而且 4 比长度为 1 的子序列的最后一个元素 3 大，此时长度为 2 的子序列有两种情况，[ 3, 4 ] 或者 [ 3, 8 ] ，和上面同理，能与 [ 3, 8 ] 构成递增子序列的元素，也可以与 [ 3, 4 ] 构成递增子序列，但能与 [ 3, 4 ] 构成递增子序列的元素，不一定能与 [ 3, 8 ] 构成递增子序列。所以长度为 2 的子序列的最后一个元素更新为 4.

 当访问 nums[ 4 ] 时，7 比 4 大，可以与 [ 3, 4 ] 构成递增子序列，此时长度为 3 的子序列的最后一个元素为 7。

当访问 nums[ 5 ] 时，2 比 3 小，和上面同理，长度为 1 的子序列的最后一个元素更新为 2.

当访问 nums[ 6 ] 时，14 比 7 大，可以构成递增子序列，此时长度为 4 的子序列的最后一个元素为 14。

当访问 nums[ 7 ] 时，13 比 14 小，但比 7 大，此时长度为 4 的子序列的最后一个元素为 14。

 

从上述过程可以看出，假设用数组 ret 来保存长度为 x 的子序列的最后一个元素，当前数组的长度为 n：

• 当前遍历到的元素 a 比 当前长度最长的子序列的最后一个元素大时， 即 a 大于数组的最后一个元素，则递增子序列的长度+1，即数组 ret 的长度 n++，且 ret [ n ] =  a；
• 当前遍历到的元素 a 比 当前长度最长的子序列的最后一个元素小时，则需要在数组中找到大于等于 a 的数中的最小值，然后用 a 把这个数覆盖掉。

思想就是让 ret 中存储比较小的元素。这样，ret 未必是真实的最长上升子序列，但长度是对的，只能说明我们曾经得到过这一长度的递增子序列。

如何快速在数组中找到大于等于 a 的数中的最小值？

用二分查找思想，根据数组元素的更新策略，可以看出数组中的元素是递增的，假设在数组中第一个大于等于 a 的数的下标为 i，数组的长度为 n，那么数组可以被划分为两部分，下标范围为 [ 0, i-1 ] 的数都比 a 小，下标范围为 [ i , n-1 ] 的数都大于等于 a，此二段性可以帮助我们快速定位要把元素 a 放在哪里。 

代码：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> ret;ret.push_back(nums[0]);int n=nums.size();for(int i=1;i<n;i++){int x=nums[i];if(x>ret.back()){ret.push_back(x);}else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(ret[mid]<x)  left=mid+1;else    right=mid;}ret[left]=x; }}return ret.size();   }
};

递增的三元子序列

334. 递增的三元子序列 - 力扣（LeetCode）https://leetcode.cn/problems/increasing-triplet-subsequence/description/

题解：

和上一题同理，如果 ret 数组的长度为 3，说明存在递增的三元子序列，此时直接返回 true 即可。

代码：

class Solution {
public:bool increasingTriplet(vector<int>& nums) {vector<int> ret;ret.push_back(nums[0]);int n=nums.size();for(int i=1;i<n;i++){if(nums[i]>ret.back()){ret.push_back(nums[i]);if(ret.size()==3)return true;}else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(ret[mid]<nums[i])    left=mid+1;else right=mid;}ret[left]=nums[i];}}return false;}
};

简易版：

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int first=nums[0],second=INT_MAX;for(int i=0;i<nums.size();i++){if(nums[i]>second) return true;else if(nums[i]>first)  second=nums[i];else first=nums[i];}return false;}
};

最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

题解：

本题其实是一个滑动窗口。注意窗口不要越界，且窗口左闭右开。left 是窗口的左端点，right 是窗口的右端点。

代码： 

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int left=0,right=0,n=nums.size(),ret=0;while(left<n){right=left+1;while(right<n && nums[right]>nums[right-1])right++;ret=max(ret,right-left);//左闭右开left=right;}return ret;}
};