Posted on 2022-11-09 23:42
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
数据结构 、
闲来无事重切Leet Code
给一列温度值，问对于第i天，要等多少天，温度才会大于当前第i天的值
栈操作，从序列最后一位开始处理，如果遇到更高的温度就不断pop栈顶，栈中只需要记录保留下来的日期，可以不用记录那一日的温度值（但很奇怪的是我同时记录温度值反而Memory用得少。。）
以下为两个版本的代码
Version1：不记录温度值
1 #739
2 #Runtime: 3649 ms
3 #Memory Usage: 27.2 MB
4
5 class Solution(object):
6 def dailyTemperatures(self, temperatures):
7 """
8 :type temperatures: List[int]
9 :rtype: List[int]
10 """
11 stk = []
12 stk.append([1])
13 ans = []
14 ans.append(0)
15 for i in range(len(temperatures)-2, -1, -1):
16 while len(stk) > 0 and temperatures[i] >= temperatures[len(temperatures) - stk[-1][0]]:
17 stk.pop(-1)
18 if len(stk) > 0:
19 ans.append((len(temperatures) - i) - stk[-1][0])
20 else:
21 ans.append(0)
22 stk.append([len(temperatures) - i])
23 ans.reverse()
24 return ans
25
Version2：记录温度值
1 #739
2 #Runtime: 3789 ms
3 #Memory Usage: 26.9 MB
4
5 class Solution(object):
6 def dailyTemperatures(self, temperatures):
7 """
8 :type temperatures: List[int]
9 :rtype: List[int]
10 """
11 stk = []
12 stk.append([temperatures[-1], 1])
13 ans = []
14 ans.append(0)
15 for i in range(len(temperatures)-2, -1, -1):
16 while len(stk) > 0 and temperatures[i] >= stk[-1][0]:
17 stk.pop(-1)
18 if len(stk) > 0:
19 ans.append((len(temperatures) - i) - stk[-1][1])
20 else:
21 ans.append(0)
22 stk.append([temperatures[i], len(temperatures) - i])
23 ans.reverse()
24 return ans