JS:在迭代这个数组时，可以使用哈希映射来跟踪吗?

Question

我正在尝试练习一些算法问题，但我被难住了解决这个问题的最佳方法。 我显然可以嵌套循环，但这似乎效率不高。 我可以使用哈希图来跟踪温度和温度的索引吗？

给定每日温度列表，生成一个列表，对于输入中的每一天，告诉您要等到温度升高多少天。如果没有可能的未来日期，请改为 0。 例如，给定列表温度 = [73， 74， 75， 71， 69， 72， 76， 73]，则输出应为 [1， 1， 4， 2， 1， 1， 0， 0]。

Answer 1

您可以使用几种不同的技巧。 @PlatypusMaximus试图指出一个在你从最后迭代时有效的方法，但你也可以在向前迭代时做到这一点，我认为这样更容易理解：

1. 循环访问数组时，会保留一个索引列表，这些索引尚未为其分配"最近的温暖日"。 此列表最初为空。

2. 对于每个元素，从列表中删除所有温度较低的索引，并将其"最接近的温暖日"分配给当前索引。

3. 当你到达最后时，列表中剩余的任何索引都没有"最接近的温暖日"，并得到0。

诀窍是：每当将元素添加到列表中时，前面的所有元素都相等或更大。 因此，指数列表仍按温度降序排序。 在步骤 (2( 中，这意味着您只需要查看列表末尾的元素(您可以使用堆栈(而不是搜索它，结果是整个过程需要 O(N( 时间。

Answer 2

您可以用零填充结果数组，并通过检查存储的值作为对象中的键和索引作为值来迭代给定的值。

如果找到一个大于临时对象中的值的值，则在索引处分配其他索引的增量，并从对象中删除此键。

将每个索引分配给对象，并将温度作为键。

var data = [73, 74, 75, 71, 69, 72, 76, 73],
//     [ 1,  1,  4,  2,  1,  1,  0,  0]
result = Array.from(data, _ => 0);
data.reduce((t, v, i) => 
t.filter(([w, j]) => {
if (w >= v) return true;
result[j] = i - j;
}).concat([[v, i]]),
[]
);
console.log(result);