Leetcode-739 Daily Temperatures

发表于 | 分类于 | 次

Daily Temperatures

Given a list of daily temperatures T, return a list such 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 of temperatures T = [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].

解题思路

法一：从后往前遍历 T，对于当前温度 t 及其索引 i，取温度 t+1~100 中的最小索引 j，在温度 t 的那一天 i 需等待 j-i 天。最后更新 t 的索引为 i。

法二：要找比当天温度高的下一天，考虑用递减栈，栈内温度递减。以 i 遍历数组，若栈不为空且当前温度大于栈顶温度 t，必须出栈以保持递减性，此时在温度 t 的那一天 j 需等待 i-j 天。否则，当前温度的索引入栈，等待温度高的那一天到来。

复杂度分析

  • 时间复杂度：法一 $O(wn)$，w 为温度种数；法二 $O(n)$，每个元素最多进栈出栈各一次。
  • 空间复杂度：法一 $O(n+w)$，保存结果和温度索引；法二栈中最多需要保存 n 个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution_1 {
public:
	vector<int> dailyTemperatures(vector<int>& T) {
		int n = T.size();
		vector<int> res(n);
		vector<int> lastpos(101, n);
		for (int i = n - 1; i >= 0; --i) {
			int wi = n;
			for (int j = T[i] + 1; j <= 100; ++j) {
				if (lastpos[j] < wi) wi = lastpos[j];
			}
			if (wi < n) res[i] = wi - i;
			lastpos[T[i]] = i;
		}
		return res;
	}
};

class Solution_2 {
public:
	vector<int> dailyTemperatures(vector<int>& T) {
		int n = T.size();
		vector<int> res(n, 0);
		stack<int> st;
		//栈中会保存相同元素多次
		for (int i = 0; i < T.size(); ++i) {
			while (!st.empty() && T[i] > T[st.top()]) {
				auto t = st.top(); st.pop();
				res[t] = i - t;
			}
			st.push(i);
		}
        
		//栈中相同温度只存一个
		//for (int i = n - 1; i >= 0; --i) {
		//	while (!st.empty() && T[i] >= T[st.top()]) st.pop();
		//	if (st.empty()) res[i] = 0;
		//	else res[i] = st.top() - i;
		//	st.push(i);
		//}
        
		return res;
	}
};