Javascript:检查数组是否是几乎递增的序列

Question

我正在处理 Code Signal 上的一些 Javascript 挑战，并遇到了这个问题:

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.**

Note: sequence a0, a1, ..., an is considered to be a strictly increasing if a0 < a1 < ... < an. Sequence containing only one element is also considered to be strictly increasing.

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].

我的方法是迭代序列数组，检查当前元素是否大于下一个元素，如果是则删除当前元素。然后，增加一个计数器，如果计数器小于2则返回true，否则返回false。

这是我的代码:

function almostIncreasingSequence(sequence) {
    // If array has 1 or 2 elements it passes
    if(sequence.length <= 2) {
        return true;
    }

    // Keeps track of numbers removed
    let numberRemoved = 0;

    // Iterate through array, check if current element is greater than next element
    // If so, increment numberRemoved and remove current element
    for(let i = 0; i < sequence.length; i++) {        
        if(sequence[i] >= sequence[i + 1]) {
            numberRemoved++;

            // Removed element if it's greater than next element
            let removed = sequence.splice([i], 1);
            i = 0;

            console.log(sequence);
        }

    }

    // Second pass through the array checks if there are 2 or more out of order        
    // elements. Inefficient and sloppy, need to find a better approach
    for(let j = 0; j < sequence.length; j++) {
        if(sequence[j] >= sequence[j + 1]) {
            numberRemoved++;
        }
    }

    // If number is less than 2, the sequence passes
    if(numberRemoved < 2) {
        return true;
    }
    else {
        return false;
    }  
}

该解决方案解决了 17/19 个测试用例。我遇到了一种边缘情况，有时如果 i >= [i + 1] 正确的方法是删除 [i + 1]，而不是 >我。例如:

• 对于序列:[3, 5, 67, 98, 3]
• For 循环检查 98 是否 >= 3
• 删除 98
• 序列失败，因为 [3,5,67,3] 失败
• 在本例中，我们不应该删除 98，而应该删除 3
• 然后序列传递:[3, 5, 67, 98] 返回 true
• 对于这种边缘情况，我们不想这样做:letremoved=sequence.splice([i], 1);
• 我们想做的是:letremoved=sequence.splice([i + 1], 1);
• 这将删除 3
• [3, 5, 67, 98] 返回 true

我该如何处理这种边缘情况？在某些情况下，如果 sequence[i] >= [i + 1] 您需要删除 sequence[i]，在其他情况下您需要删除 [i + 1]。如何在不使用第二个 for 循环并再次遍历数组的情况下解决这个问题？

Answer 1

每当发现递减的数字时，我们需要确定应该删除两个连续数字中的哪一个。它可以是:

1. 最后一个数字太大
2. 当前数量太小

如果它们都不能修复减少的问题，则该数组已经不是“几乎递增的序列”，因为这意味着至少需要再次删除。

function almostIncreasingSequence(sequence) {
  let removed = 0;
  let i = 0;
  let prev = -Infinity;
  
  // as long as removed less than 2 times, and i is under arrays length
  while(removed < 2 && i < sequence.length) {
    if(sequence[i] > prev) { // if current is bigger the previous
      prev = sequence[i]; // assign current to previous
      // remove the latter number, if it fixes the decrease
    } else if (i === sequence.length - 1 || sequence[i+1] > sequence[i-1]) {
      removed++; // increment removed
    } else if (i < 2 || sequence[i] > sequence[i-2]) {
      // remove the former number, if it fixes the decrease
      removed++;
      prev = sequence[i];
    } else {
      // neither option fixes the decrease, so at least 2 removal is needed
      return false;
    }
    i++;
  }

  return removed < 2; // true if removed are under 2
}

console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true
console.log(almostIncreasingSequence([3, 5, 67, 98, 3])); // true
console.log(almostIncreasingSequence([4, 3, 5, 67, 98, 3])); // false
console.log(almostIncreasingSequence([1, 4, 2, 3])); // true
console.log(almostIncreasingSequence([10, 13, 2, 9])); // false