Определите, содержит ли массив почти возрастающую последовательность

Question

Учитывая последовательность целых чисел как массив, определите, возможно ли получить строго возрастающую последовательность, удалив не более одного элемента из массива.

Для последовательности = [1, 3, 2, 1]выход должен быть

almostIncreasingSequence(sequence) === false

В этом массиве нет ни одного элемента, который можно было бы удалить, чтобы получить строго возрастающую последовательность.

Для последовательности = [1, 3, 2]выход должен быть

almostIncreasingSequence(sequence) === true

Как вы можете удалить 3 из массива, чтобы получить строго возрастающую последовательность [1, 2], Кроме того, вы можете удалить 2, чтобы получить строго возрастающую последовательность [1, 3],

Вот что у меня так далеко:

function almostIncreasingSequence(sequence) {
  //compare current int to previous, return true if greater than 
  //remove int at index and compare with new values, return false if comparison fails
  var result = false;

  for(var i = 0; i < sequence.length; i++){
     var newSequence = sequence.slice();
     var subSequence = newSequence.splice(i, 1);

     for(var j = 0; j < newSequence.length - 1; j++){
        if(newSequence === newSequence.sort((a,b) => a < b).reverse()){
          result = true;
        } 
     }         
  }
  return result;
}

Я пытаюсь выяснить, как решить эту проблему. Я чувствую, что я очень близок, но по какой-то причине, когда я вызываю reverse в условном выражении, он также сортирует переменную newSequence. Он сортирует две переменные в условной, а не одну. В результате это решает к истине. Мне не понятно, почему это происходит. Любые отзывы приветствуются.

Answer 1

Нет необходимости использовать вложенный цикл или создавать новые массивы. Это можно сделать за O(n) раз:

function almostIncreasingSequence(sequence) {
    var prev = -Infinity,
        beforePrev = -Infinity,
        allowExceptions = true;
    
    for (var curr of sequence) {
        // Is order not maintained?
        if (curr <= prev) {
            // Give up when this is not the first exception
            if (!allowExceptions) return false;
            allowExceptions = false;
            // Decide whether to skip the current or previous value
            if (curr > beforePrev) prev = curr;
        } else { // Normal case: keep track of two preceding values
            beforePrev = prev;
            prev = curr;
        }
    }
    return true;
}

console.log(almostIncreasingSequence([1,5,3,4,8])); // true
console.log(almostIncreasingSequence([1,5,0,6,8])); // true
console.log(almostIncreasingSequence([1,5,0,4,8])); // false

Answer 2

sort() изменяет массив на месте, он не возвращает новый массив. И вы не можете сравнить содержимое двух массивов, используя ==, так что это не хороший способ определить, отсортирован ли массив. Вы можете просто перебрать массив, проверяя, больше ли каждый элемент, чем предыдущий.

function almostIncreasingSequence(sequence) {
  for (var i = 0; i < sequence.length; i++) {
    var newSequence = sequence.slice();
    newSequence.splice(i, 1);
    var isSorted = true;
    for (j = 1; isSorted && j < newSequence.length; j++) {
      if (newSequence[j] <= newSequence[j-1]) {
        isSorted = false;
      }
    }
    if (isSorted) {
      return true;
    }
  }
  return false;
}

console.log(almostIncreasingSequence([1, 3, 2, 1]));
console.log(almostIncreasingSequence([1, 3, 2]));
console.log(almostIncreasingSequence([1, 2, 3, 4, 5, 3]));
console.log(almostIncreasingSequence([8, 1, 2, 3, 4, 5]));
console.log(almostIncreasingSequence([8, 1, 2, 2, 4, 5]));