c/c++ leetcode 最长连续递增序列

文章目录

题目链接:

https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

给定一个未经排序的整数数组，找到最长且连续的的递增序列，并返回该序列的长度。

一.滑动窗口算法

temp和存储最后答案的变量为什么初始化为1?

最短连续的递增序列长度为1;

只要nums[i] > nums[i - 1];那它就是连续的的递增序列,temp++;如果不是temp 置为1;

每次循环都把answer与temp比较长度,去最长的赋值给answer

class Solution {public:    int findLengthOfLCIS(vector
   
    & nums) {        if (nums.empty()) return 0;                int temp = 1, answer = 1;        for(int i = 1;i < nums.size();i++) {            if (nums[i - 1] < nums[i]) answer = max(answer,++temp);            else temp = 1;		}                return answer;    }};

时空复杂度分析

时间复杂度:O(n);一个for循环

空间复杂度:Q(1); 用到的是常量空间

二.动态规划

创建一个vector dp来保存状态数组中的元素初始化为1 ;

dp[i] == nums[i]之前的连续递增序列的长度;

状态转移方程: if (nums[i] > nums[i - 1]) dp[i] = dp[i- 1] + 1;

if (nums[i] <= nums[i - 1]) dp[i] = 1;

其实思路和第一种几乎一样,就是不用二个变量经常的进行赋值,用一个数组来保存nums数组所有的连续递增序列的长度;

class Solution {public:  int findLengthOfLCIS(vector
   
    & nums) {        if (nums.empty()) return 0;        vector
    
      dp(nums.size(),1);        for (int i = 1; i < nums.size(); i++) {            if (nums[i] > nums[i - 1])                 dp[i] = dp[i - 1] + 1;        }                return *max_element(dp.begin(),dp.end());    }};

时空复杂度分析

时间复杂度:O(2*N) 一个for循环一个在dp数组中找一个最大的数字返回,但O() 表示法是渐进表示方法去掉常量

为O (N);

空间复杂度: O(N) 使用了一个dp数组保存状态;

三.快慢指针

设置满指针指向0;快指针指向1走到一个递增序列的最后一个元素的下一个元素; 快指针 - 慢指针就等于这个递增序列的长度,慢指针 = 快指针;快指针++;如果faster不自增,以后递增序列都为零,因为快指针nums[faster] > nums[faster - 1];

class Solution {public:    int findLengthOfLCIS(vector
   
    & nums) {        if (nums.empty()) return 0;                int slow = 0, faster = 1, maxlen = 1;                while (faster < nums.size()) {            while (faster < nums.size() && nums[faster] > nums[faster - 1]) faster++;            maxlen = max(maxlen, faster - slow);            slow = faster;            ++faster;        }        return maxlen;    }};

时空复杂度分析

时间复杂度:O(n);一个for循环

空间复杂度:Q(1); 用到的是常量空间

四.分治算法:

借鉴与Leetcode题解:

使用分治算法把一个数组一分为二,这样的话:一共就只有三种情况:

一.左边是最长递增序列

二.右边是最长递增序列

三.最长递增序列有右边也有左边,;

我们只需要从中间往右遍历找到小于它左边的下标数据的停止

从中间往左遍历找到大于它右边下标的数据停止

二者加起来就是这个区间内的最长递增序;

class Solution {public:    int findLengthOfLCIS(vector
   
    & nums) {        if(nums.size()==0) return 0;        return helper(nums,0,nums.size()-1);    }    int helper(vector
    
     & nums,int left,int right){        if(left==right)  return 1;        int middle = left + (right-left) / 2;        int resofleft = helper(nums,left,middle);        int resofright = helper(nums,middle+1,right);        int countleft = 1; //countleft 和countright 必须有一个初始化为1;        int countright = 0;        for(int i=middle;i>left;i--){            if(nums[i]>nums[i-1]) countleft++;            else break;        }        for(int i=middle;i
     
      nums[i]) countright++;            else break;        }        int countofmiddle = countright + countleft;                return max(max(countofmiddle,resofleft),resofright);    }};

作者：forfut

链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/solution/cyi-ci-bian-li-he-fen-zhi-suan-fa-by-forfut/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时空复杂度分析;

时间复杂度: 每次进入函数就要遍历这个区间一次,为O(N) 一分为二进入函数为(long2N)次,总的复杂度为O(N*logN);

空间复杂度:就是递归树的深度为O(logN);

你可能感兴趣的文章

深入浅出：Tomcat应用服器中Servlet容器架构及工作原理剖析