739.|739. Daily Temperatures（week7）
739. 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].
解题思路
【739.|739. Daily Temperatures（week7）】简单的说，这道题需要我们找到某个数组元素后面的最早出现的元素。简单的思路就是：从这个点出发，找后面的所有点，是否有比它还要大的元素；如果出现了，就记录下二者下标的差值；若没有，则记录下0。这是一种可取的思路，假设平均在后面的第k个点才找到符合要求的值，那么这个算法的复杂度将会是O(N * K)。k的大小取决于数据，如果这是一个从大到小排列的序列，那么K = n/2。复杂度将会是O(n^2)的规模。而题目给出的数组大小会达到30000，很显然，这种方法是不可取的。
在上述的方法中，对每一个点，我们都遍历了太多不符合要求的点。最好的情况是，对于每一个点，我们只需要知道它自己的值以及第一个符合要求的值即可，那么我们要如何实现呢？考虑用一个栈结构来存储这个列表。对于每一个元素，我们在进栈之前，先判断栈顶元素是否比它要小，若比它要小，则栈顶元素最早出现的比它自身大的元素就是当前的元素，出栈并继续判断；若栈顶元素不比它小，则进栈。这样一来，每一个元素我们最多只会对它进行一次入栈和出栈的操作，这样一来，复杂度就会由O(N * K)下降到O(2n)。而付出的代价是，多维护了一个栈空间。
时间复杂度分析
对于每一个元素而言，最多只进行一次入栈和出栈的操作，复杂度为O(n)。
空间复杂度分析
能够存下n个元素的栈以及返回的结果，复杂度为O(n)。
源码
class Solution {
public:
vector dailyTemperatures(vector& T) {
stack Tstack;
map next;
for (int i = 0;
i < T.size();
++i) {
if (Tstack.empty()) {
Tstack.push(i);
} else {
while (!Tstack.empty()) {
int topIndex = Tstack.top();
if (T[i] > T[topIndex]) {
Tstack.pop();
next[topIndex] = i - topIndex;
} else {
break;
}
}
Tstack.push(i);
}
}
while (!Tstack.empty()) {
next[Tstack.top()] = 0;
Tstack.pop();
}
vector result;
for (int i = 0;
i < T.size();
++i) {
result.push_back(next[i]);
}
return result;
}
};
推荐阅读
- Daily|Daily knowledge
- DailyTopic_4/16 B站（最有YouTube气质的视频网站）
- 属于我的绘本系列APug'sDailyLife（4）
- 回归本质（daily|回归本质：daily stand第一波--理论与流程。整体思路。）
- 英语|2012-06-11 Daily English
- 2012-06-12 Daily English
- 桑币笔记|桑币笔记 Zombit Daily 投资日报 01.17
- daily|daily expression
- Daily|Daily Scrum 每日站会
- Daily|Daily note 20190417