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

Question

没什么思路啊，题目如下
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

[time limit] 4000ms (js)
[input] array.integer sequence

Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

有个思路：2层循环，第一循环移除元素，第二层循环判断移除这个元素后是否有自增序列。

Answer 1

Provide an idea

Create a difference-by-difference array: For example, a=[1,3,2,1], and after difference-by-difference, we get [2,-1,-1]

The so-called deletion of an element means removing the head or tail in a difference-by-difference array, or adding two adjacent elements into one element.

Therefore, if there is more than one negative number in the difference array, it does not work; if there is no negative number, it does; otherwise, the above operation is performed on the only negative number. If it can be deleted or merged into a positive number, it does

In this way, the time complexity can be reduced to O(n)

Answer 2

Can be done at O(n) time:

1. for each adjacent [a, b]，判断是否 a >= b. Such number pairs destroy strict incrementality. If there is more than one such pair, return false. If there is none, return true.

2. If there is only one pair in 1, is it still incremented after [a0, b0]，判断 "移除a0或b0" and returns

Answer 3

The result is correct, but it exceeds the specified time. Is there a better way?

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;
}

Method with time complexity of 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;
}

Answer 4

Is this counting the number of reverse numbers?