javascript - 数组中的序列

Question

我有一个算法练习要做，但我不知道该怎么做，因为要求是只使用基本的编程概念。所以 - 关键是在一个数组中找到最长的数字序列，这些数字正在增长或不改变值。

所以对于数组 [1,1,2,4,0,1,7,4]，它将是 [1,1,2,4]。

它应该具有尽可能小的时间和内存复杂度。任何解决方案，提示？非常感谢您的任何建议或反馈。

这就是我在过去 10 分钟内设法做到的，但我觉得我正在以最复杂的方式做到这一点......

function idk(array) {
  
  var current = 0;
  var winner = 0;

  var currentArray = [];
  var winnerArray = [];

  for (let i = 0; i <= array.length; i++) {

    if (array[i + 1] >= array[i]) {

      currentArray.push(array[i]);
      current = currentArray.length;

    } else {

      currentArray.push(array[i]);

      if (currentArray.length > best.length) {

        // copy array and append it to the new array?

      }

    }

    }
    return winnerArray;
  }

标签： javascriptpythonalgorithm

Answer 1

为什么要遍历数组的末尾？

因为您可以利用这个优势来收集最后一个最长的序列，而无需在循环后检查是否找到了最长的序列。

但在部分：

为什么不是临时数组？因为没有必要使用它，如果您收集值。序列的 startignn 索引很重要，实际的 indec 决定序列是否长于先前找到的序列。

循环具有两个条件，一个用于继续循环，如果在序列中，另一个用于检查实际结束的序列是否更长。并用于存储实际索引。

检查未定义值的最后一个循环是false，它不会继续循环，并且 nect 检查会显示新的最长序列或没有。

其他一些注释：

• winnerArray必须是一个空数组，因为稍后要检查length
• 序列检查取前一个元素，因为循环从第一个索引开始，并且给出了前一个元素。
• 大O是 O(n)。

function idk(array) {
    let winnerArray = [],
        index = 0;

    for (let i = 1; i < array.length + 1; i++) {
        if (array[i - 1] <= array[i]) continue;
        if (i - index > winnerArray.length) winnerArray = array.slice(index, i);
        index = i;
    }
    return winnerArray;
}

console.log(...idk([1, 1, 2, 4, 0, 1, 7, 4])); // [1, 1, 2, 4]
console.log(...idk([1, 8, 1, 1, 5, 7, 2, 2])); // [1, 1, 5, 7]
console.log(...idk([1, 8, 1, 1, 5, 7, 2, 2, 2, 2, 2]));