LeetCode739:每日温度【哈希表+二分查找】

问题分析

直接暴力搜索的时间复杂度较高，因此需要寻找更高效的解决方案。观察到温度范围有限（0-100），可以使用哈希表来记录每个温度出现的索引。具体步骤如下：

• 构建一个哈希表，键为温度值，值为该温度出现的所有索引列表。
• 遍历温度数组，对于当前温度t，查找温度范围 [t + 1, 100] 中的所有温度对应的索引列表。
• 使用二分查找在这些索引列表中找到比当前索引大的最小索引。
• 计算并更新结果数组中的值。

代码实现

from collections import defaultdictfrom bisect import bisect_leftclass Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:tempDict = defaultdict(list)n = len(temperatures)for i, t in enumerate(temperatures):tempDict[t].append(i)ans = [0] * nfor i, t in enumerate(temperatures):smallIndex = float('inf')for biggerT in range(t + 1, 101):if tempDict[biggerT]:idx = bisect_left(tempDict[biggerT], i)if idx < len(tempDict[biggerT]):smallIndex = min(smallIndex, tempDict[biggerT][idx])if smallIndex != float('inf'):ans[i] = smallIndex - ireturn ans

总结

通过哈希表和二分查找相结合的方法，可以高效地解决每日温度问题。这种方法不仅适用于本题，还可以应用于其他类似的问题，如矩形包含点的计数等。在调试过程中，需要注意细节，例如正确使用范围函数 range(x, y) 而不是 (x, y)。