javascript:如何使函数运行得更快

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.

所以除了一个问题，我的代码可以正常工作——它必须通过 30 次测试，时间限制为 4000 毫秒，但每次都会在第 30 次测试时超时。我曾尝试修改它以使其运行得更快，但每次我这样做时它都无法正常工作。尽管从技术上讲我只需要编写一个函数，但我将其分解为三个独立的函数。这是我的代码:

var greater = function(a, b) {
  if (a < b) {
    return true
  } else {
    return false
  }
}

function greaterThan(arr) {
  for (var i = 0; i < arr.length-1; i++) {
    var curr = arr[i]
    var next = arr[i + 1]
    if (greater(curr, next) === false) {
      return false
    }
  }
  return true
}

function almostIncreasingSequence(sequence) {
  for(var i = 0; i < sequence.length; i++) {
    var newArr = sequence.slice()
    newArr.splice(i, 1)
    if (greaterThan(newArr) === true) {
      return true
    } 
  }
  return false
}

那么如何在不使用两个 for 循环/迭代的情况下让它运行得更快呢？

Answer 1

改进算法可能比改进代码带来更好的结果。问题是:

1. 如果序列在索引 i 处不是严格递增的, 这样 a[i]>=a[i+1]是真的，或者a[i]或 a[i+1]必须移除以使数组严格递增 - 它们不能都留在原地。

2. 如果输入数组可以通过只删除一个元素来固定，并且它在 i 之后递减第 th 个元素，它必须通过删除带有下标 i 的元素而严格增加或 (i+1) .

比较返回前检查原数组和至多两个子数组的效率true或 false , 检查与原始数组长度相同的数组数。我会把重写代码留给你——这不是我的作业:-)