题解 | #牛牛的数列#

牛牛的数列

http://www.nowcoder.com/practice/f2419f68541d499f920eac51c63d3f72

题意:

  • 给定一个整数序列,取一个连续的子序列,要求满足:最多改变一个数,使该子序列严格上升。

方法一:

解题思路:

  • 遍历数组的元素,记为nums[i],如果nums[i+1]>nums[i-1]+2的话,无论nums[i]为什么数,那么nums[i-1],nums[i],nums[i+1]在最多一次的合理替换中可以变成一个严格上升的序列。寻找到在nums[i]左边以nums[i-1]结束的最长严格上升连续序列,以及在nums[i]右边找到以nums[i+1]开始的最长严格上升连续序列,将两者加起来为一个严格上升连续序列,遍历数组元素nums[i]求出最大值即可。

代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    //寻找以i结尾的最长连续严格递增序列长度
    int left(vector<int>& nums,int i){
        int maxLength=1;
        for(int tmp=i;tmp>=1;tmp--){
            if(nums[tmp]>nums[tmp-1])
                maxLength++;
            else 
                break;
        }
        return maxLength;
    }
    //寻找以i开始的最长连续严格递增序列长度
    int right(vector<int>& nums,int i){
        int maxLength=1;
        for(int tmp=i;tmp<=nums.size()-2;tmp++){
            if(nums[tmp]<nums[tmp+1])
                maxLength++;
            else 
                break;
        }
        return maxLength;
    }
    int maxSubArrayLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=2)
            return n;
        int ans=2;
        for(int i=1;i<n-1;i++){
            //改变nums[i]后满足递增条件,则连接前后递增序列
            if(nums[i+1]>=nums[i-1]+2)
                ans=max(ans,left(nums,i-1)+right(nums,i+1)+1);
            //不满足,则只能找单边的递增序列
            else
                ans=max(ans,max(left(nums,i-1)+1,right(nums,i+1)+1));
        }
        //根据起始序列如X,1,X,X 讨论改变第一位和改变最后一位的情况
        if(nums[1]==1)
            //第二位为1,则第一位不可能加入到递增序列中
            ans=max(ans,max(left(nums,n-2)+1,right(nums,1)));
        else
            //其他情况下第一位可以加入到递增序列中
            ans=max(ans,max(left(nums,n-2)+1,right(nums,1)+1));
        return ans;
    }
};

复杂度分析:

时间复杂度:,n为数组nums大小。遍历数组nums,每次遍历执行两次对数组的循环搜索,所以
空间复杂度:,常数个临时变量。

方法二:

解题思路:

  • 针对方法一中的循环调用left()及right()两个函数来求最长递增序列的冗余,可以利用动态规划将递增序列长度值先求出来。

图片说明

代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int maxSubArrayLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=2)
            return n;
        int ans=2;
        //初始化left.right数组
        vector<int> left(n,1),right(n,1);
        //left[i]代表以i结尾的最长递增连续子序列长度
        for(int i=1;i<=n-1;i++){
            if(nums[i]>nums[i-1])
                left[i]=left[i-1]+1;
        }
        //right[i]代表以i开始的最长递增连续子序列长度
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1])
                right[i]=right[i+1]+1;
        }
        for(int i=1;i<n-1;i++){
            //改变nums[i]后满足递增条件,则连接前后递增序列
            if(nums[i+1]>=nums[i-1]+2)
                ans=max(ans,left[i-1]+right[i+1]+1);
            //不满足,则只能找单边的递增序列
            else
                ans=max(ans,max(left[i-1]+1,right[i+1]+1));
        }
        //根据起始序列如X,1,X,X 讨论改变第一位和改变最后一位的情况
        if(nums[1]==1)
            //第二位为1,则第一位不可能加入到递增序列中
            ans=max(ans,max(left[n-2]+1,right[1]));
        else
            //其他情况下第一位可以加入到递增序列中
            ans=max(ans,max(left[n-2]+1,right[1]+1));
        return ans;
    }
};

复杂度分析:

时间复杂度:,为left,right数组赋值,遍历数组nums也是
空间复杂度:,left,right数组额外空间。

全部评论

相关推荐

2 2 评论
分享
牛客网
牛客企业服务