时间戳

首页 > 解决方案 > JS：可以在迭代这个数组时使用哈希映射来跟踪吗？

javascript - JS：可以在迭代这个数组时使用哈希映射来跟踪吗？

问题描述

我正在尝试练习一些算法问题，但我很难找到解决这个问题的最佳方法。我显然可以嵌套 for 循环，但这似乎效率不高。我可以使用哈希映射来跟踪 temp 的 temp 和 index 吗？

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

标签： javascriptalgorithm

解决方案

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

  1. 当您遍历数组时，您会保留一个未分配“最近的温暖日”的索引列表。此列表最初为空。

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

  3. 当您到达最后时，列表中剩余的任何索引都没有“最近的温暖的一天”，并且得到 0。

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

推荐阅读