我正在解决一个编程问题，并停留在拼图的最后一块。
这是个问题：https://leetcode.com/problems/daily-temperatures/
我有一个排序(值(字典，现在我想对字典进行log(n(复杂性搜索。这是我到目前为止编写的代码。
def dailyTemperatures(self, T):
if len(T) == 0:
return []
if len(T) == 1:
return [0]
R = [None] * len(T)
#create map, populate map
M = {}
for i in range(0, len(T)):
M[i] = T[i]
#sort map by value(temps)
MS = sorted(M.items(), key=lambda x: x[1])
for i in MS:
print(i[0], i[1])
for i in range(0,len(T)):
t = T[i] #base value for comparison
R[i] = 0
x = 0
# find smallest x for which temp T[x] > T[i]
# Dictionary is sorted for Temps
R[i] = x - i
return R
循环中注释的部分是我遇到麻烦的地方。我在任何地方都找不到答案，可以搜索排序的字典，然后按键过滤。
也非常感谢任何解决此问题的提示或新建议。
您的代码可能会起作用，但是： 由于需要回溯索引，该算法实际上只是在天真的蛮力气泡排序类算法之上增加了更多复杂性层。
最简单的修改只是搜索比当前索引>的最小索引。 将字典.items()中的位置存储为值的一部分，以便您可以检索它。 但是，您不能对索引进行二分搜索，因为它是按值排序的，并且索引不是按顺序排列的。 这应该为您提供可接受的 O(N( 查找。
最后，您仍然必须按索引搜索(索引优先于温度(。 即使使用二分搜索，您尝试的算法，忽略预排序的 N log N 复杂性，充其量仍然需要 O(N * log N * log N( 进行搜索。 您当前的尝试实际上是 O(N^2 log N(，但使用第三个缓存索引表，最近的索引查找可以转换为日志 N。
这将是一个非常复杂和低效的算法，因为基本上不得不回溯你的搜索顺序。 而且它比天真的蛮力没有任何优势(客观上更糟(.
注意：关键点是你需要最近的索引，如果你按 value
如果你仍然想这样做(我猜是一个代码高尔夫挑战(，你会想在字典.items()添加它的位置索引到你的字典中， 因此，当您在 dict 中查找密钥时，您可以通过温度排序列表找到开始搜索的起始位置。 要获取日志 N，您需要存储每个温度范围及其索引范围。 这部分的实现可能特别复杂。 当然，您需要实现二叉搜索算法。
堆栈算法：
以下算法的基本思想是，任何较低的温度都不再重要.
eg： [...] 10>20<9 6 7 21. 20岁以后;9 6 7(或任何<= 20(无关紧要。 9点以后;6 和 7 无关紧要。 等。
因此，从末尾迭代，将数字添加到堆栈中，弹出的堆栈编号小于当前数字。
请注意，由于温度的数量绑定为 70 个值，并且在每次迭代时都会从堆栈中删除小于当前温度的数字，因此搜索下一个温度的复杂性和堆栈的大小都绑定为 70。 换句话说，constant.
所以对于T中的每个项目，在最坏的情况下，您最多搜索70个值，即：len(T( * 70。 因此，该算法的复杂度为 O(N(：T 中的项数。
def dailyTemperatures(T):
res = [0]*len(T)
stack = []
for i, x in reversed([*enumerate(T)]):
if len(stack) < 1:
stack.append((i,x))
else:
while(len(stack)>0 and stack[-1][1]<=x):
stack.pop()
if len(stack)>0 and stack[-1][1]>x:
res[i] = stack[-1][0] - i
print(x, stack)
stack.append((i,x))
return res
print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))