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

Fournir une idée

Créez un tableau différence par différence : par exemple, a=[1,3,2,1], et après différence par différence, nous obtenons [2,-1,-1]

La soi-disant suppression d'un élément signifie supprimer la tête ou la queue dans un tableau différence par différence, ou ajouter deux éléments adjacents en un seul élément.

Par conséquent, s'il y a plus d'un nombre négatif dans le tableau de différence, cela ne fonctionnera pas ; s'il n'y a pas de nombre négatif, cela fonctionnera sinon, l'opération ci-dessus sera effectuée sur le seul nombre négatif ; peut être supprimé ou fusionné en un nombre positif, cela fonctionnera

De cette façon, la complexité temporelle peut être réduite à O(n)

Answer 2

Peut être fait à O(n)heure :

1. Pour chaque [a, b] adjacent, déterminez s'il s'agit de a >= b. De telles paires de nombres détruisent la stricte incrémentalité. S'il existe plusieurs de ces paires, renvoyez false. S'il n'y en a pas, retournez vrai.

2. S'il n'y a qu'une seule paire de [a0, b0] en 1, déterminez "si elle augmente encore après avoir retiré a0 ou b0" et retournez

Answer 3

Le résultat est correct, mais il dépasse le temps spécifié. Existe-t-il une meilleure solution ?

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

Méthode avec complexité temporelle de 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

Est-ce que cela compte le nombre de nombres inversés ?