比较数组中的相邻元素并选择每对中较小的一个

Question

我正在学习 JS 算法课程。这是讲师对一个问题的解决方案，它运行成功：

function arrayPreviousLess(items) {
  const lessThanList = []

  for (let i = items.length - 1; i >= 0; i--) {
    for (let j = i; j >= 0; j--) {
      if (items[i] > items[j]) {
        lessThanList.unshift(items[j])
        break
      } else if (j === 0) {
        lessThanList.unshift(-1)
      }
    }
  }

  return lessThanList
}


console.log(arrayPreviousLess([3, 5, 2, 4, 5]))

此代码比较相邻的数组项。如果前一项小于下一项，则 return 较小。如果为 false，则必须 return -1，如下例：

输入：

[3,5,2,4,5]

输出：

[-1,3,-1,2,4]

我什么都懂，除了让 break 进入循环的目的是什么？当我删除这个 break 它以同样的方式工作。

Answer 1

考虑到相邻对的问题描述，您展示的算法没有多大意义。除了 break 之外，没有理由使用嵌套循环，除非目的是将每个元素与其先前元素的 all 进行比较，在这种情况下它是正确的。无论哪种方式，unshift 都比 push 慢得多，而且我认为无论算法如何，都没有理由求助于此函数，我也看不到反向外循环背后的原因。

我会使用 map 为相邻对编写函数。我们可以在一次迭代中完成此操作。

const arrayPreviousLess = a => a.map((e, i) => a[i-1] < e ? a[i-1] : -1);

[
  [3, 5, 2, 4, 5],
  [1],
  [1, 2],
  [2, 1],
  [1, 2, 3],
  [3, 2, 1],
  [3, 2, 3],
  [3, 1, 6, 4, 5],
].forEach(e => console.log(`[${e}] => [${arrayPreviousLess(e)}]`));

另一方面，如果问题是将每个元素与其左侧的所有元素进行比较，我会修改讲师的解决方案以至少避免 unshift 并从前到后遍历参数数组.

const arrayPreviousLess = a => a.map((e, i) => {
  while (i--) {
    if (a[i] < e) return a[i];
  }

  return -1;
});

[
  [3, 5, 2, 4, 5],
  [1],
  [1, 2],
  [2, 1],
  [1, 2, 3],
  [3, 2, 1],
  [3, 2, 3],
  [3, 1, 6, 4, 5],
].forEach(e => console.log(`[${e}] => [${arrayPreviousLess(e)}]`));

该算法仍然是二次算法，但有一个使用堆栈的线性算法。对于每个元素，当堆栈不为空且当前元素小于堆栈顶部时，弹出堆栈。最终，堆栈要么变空，要么栈顶包含前一个较小的元素。如果堆栈变空，则将元素映射到 -1，否则将元素映射到前一个较小的元素。最后将当前元素压入栈中。

const arrayPreviousLess = a => {
  const stack = [];  
  return a.map(e => {
    while (stack.length && e < stack[stack.length-1]) {
      stack.pop();
    }

    return stack.push(e) > 1 ? stack[stack.length-2] : -1;
  });
};

[
  [3, 5, 2, 4, 5],
  [1],
  [1, 2],
  [2, 1],
  [1, 2, 3],
  [3, 2, 1],
  [3, 2, 3],
  [3, 1, 6, 4, 5],
].forEach(e => console.log(`[${e}] => [${arrayPreviousLess(e)}]`));

这背后的直觉是，当前元素后面任何大于它的先前元素永远不可能是先前最小的候选者。我们可以丢弃它们。本质上，我们保留了最小候选元素的历史记录，并在我们可以保证前面有一些较小的元素时立即删除任何候选元素。

比较数组中的相邻元素并选择每对中较小的一个

Comparing adjacent elements in an array and selecting the smaller of each pair

javascript

arrays

algorithm

for-loop

break