# 739. Daily Temperatures 每日温度

@TOC

## # 题目描述

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

``````For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
``````

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

## # 解题方法

### # 倒序遍历

``````class Solution(object):
def dailyTemperatures(self, temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
save = {}
for day in range(len(temperatures) - 1, -1, -1):
temp = temperatures[day]
save[temp] = day
larger = []
for i in range(temp + 1, 102):
if i in save:
larger.append(save[i] - day)
if larger:
else:
``````

### # 栈

``````class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
N = len(T)
stack = []
res = [0] * N
for i, t in enumerate(T):
while stack and stack[-1][0] < t:
oi = stack.pop()[1]
res[oi] = i - oi
stack.append((t, i))
return res
``````

C++版本的代码如下：

``````class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
const int N = T.size();
stack<pair<int, int>> s;
vector<int> res(N);
for (int i = 0; i < N; i++) {
while (!s.empty() && s.top().first < T[i]) {
int io = s.top().second; s.pop();
res[io] = i - io;
}
s.push({T[i], i});
}
return res;
}
};
``````

## # 日期

2018 年 2 月 7 日 2018 年 12 月 7 日 —— 恩，12月又过去一周了