java - 【算法题】给定int数组，移除不超过一个元素后，判断是否存在自增序列

这个是不是统计逆序数的个数？

结果是对的，但是超过规定的时间了，有更好的方法吗？

function almostIncreasingSequence(sequence) {

    var iscan = false;
    var is = true;
    var temp
    for(var i=0;i<sequence.length;i++){
        is = true;
        temp = sequence.slice(0,i).concat(sequence.slice(i+1));
        for(var j=0;j+1<temp.length;j++){
           
            if(temp[j] <= temp[j+1]){
                is = false;
                break;
            }
        }
        if(is){
            iscan=true;
            break;
        }

    }
    return iscan;
}

时间复杂度为O(n)的方法

boolean almostIncreasingSequence(int[] sequence) {
    if(sequence.length<=2){
        return true;
    }
    //找出逆序的数的index
    int count = 0;
    int biggerIndex = 0;
    int smallerIndex = 0;
    boolean isHave = true;
    for(int i=0;i+1<sequence.length;i++){
        //如果找到2组逆序，直接返回false
        if(count>1){
            isHave = false;
        }
        if(sequence[i]>=sequence[i+1]){
            count ++;
            biggerIndex = i;
            smallerIndex = i+1;
        }
    }
    
    //分别判断当移除2个数后剩下的数组是不是自增的
    for(int i=0;i+2<sequence.length;i++){
        int cur = i;
        int next = i+1;
        if(i==biggerIndex){
            continue;
        }
        if(i+1==biggerIndex){
            next = i+2;
        }
        if(sequence[cur]>=sequence[next]){
            isHave = false;
        }
    }
    if(isHave){
        return isHave;
    }else{
        isHave = true;
    }

    for(int i=0;i+2<sequence.length;i++){
        int cur = i;
        int next = i+1;
        if(i==smallerIndex){
            continue;
        }
        if(i+1==smallerIndex){
            next = i+2;
        }
        if(sequence[cur]>=sequence[next]){
            isHave = false;
           
        }
    }
    return isHave;
}

可以在 O(n) 时间做到:

1. 对每个相邻的 [a, b]，判断是否 a >= b。这样的数对破坏严格递增性。如果这样的数对超过一个，返回false。如果一个也没有，返回true。

2. 如果1中只有一对 [a0, b0]，判断 "移除a0或b0后是否还是递增" 并返回

提供一个思路

作出逐差数组: 如 a=[1,3,2,1]，逐差后得 [2,-1,-1]

所谓删除一个元素，即在在逐差数组中去头或去尾，或把相邻两个相加合并成一个元素。

因此，若逐差数组中有多于一个负数，则不行; 若无负数，则可以; 否则对惟一的负数作以上操作，若其能被删掉或被合并成正数，则可以

这样一来，时间复杂度可以降到 O(n)