JavaScript：检查数组是否是一个几乎递增的序列

Question

我正在研究一些关于代码信号的Javascript挑战，遇到了这个问题：

给定一个整数序列作为一个数组，确定是否可以通过从数组中删除不超过一个元素来获得一个严格递增的序列。**

注意：如果a0

我的方法是遍历序列数组，检查当前元素是否大于下一个元素，如果大于，则删除当前元素。然后，递增一个计数器，如果计数器小于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]，而不是移除i。例如：

• 在序列的情况下:[3,5,67,98,3]
• for循环检查98>=3
• 删除98
• 序列失败，因为[3,5,67,3]失败
• 在这种情况下，我们不应该删除98，我们应该删除3
• 然后通过序列:[3,5,67,98]返回true
• 对于这种边缘情况，我们不想做：let remove=sequence.splice([i],1）；
• 我们要做：let remove=sequence.splice([i+1],1）；
• 这将删除3
• [3,5,67,98]返回true

我如何处理这种边缘情况？在某些情况下，如果序列[i]>=[i+1]，则需要删除序列[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