LWC 61：739. Daily Temperatures
传送门：739. Daily Temperatures
Problem:
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].
思路： 求出当前元素的第一个大于它的位置即可，所以该问题就是nextGreaterElement系列，具体参考博文【 算法细节系列（10）：503. Next Greater Element II】
Java版本：
代码语言：javascript复制 public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ans = new int[n];
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> mem = new HashMap<>();
for (int i = 0; i < n; i) {
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
int nxt = stack.pop();
mem.put(nxt, i);
}
stack.push(i);
}
for (int i = 0; i < n; i) {
if (mem.containsKey(i)) {
ans[i] = mem.get(i) - i;
}
else ans[i] = 0;
}
return ans;
}Python 版本：
代码语言：javascript复制 def dailyTemperatures(self, temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
n = len(temperatures)
stack = []
map = {}
ans = [0] * n
for i in range(n):
while (len(stack) > 0 and temperatures[stack[-1]] < temperatures[i]):
nxt = stack.pop(-1)
ans[nxt] = i - nxt
stack.append(i)
return ans 
