Posted on 2022-11-09 23:42
Uriel 閱讀(68)
評論(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