题目描述
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
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
解题思路
- 暴力（Time Limit Exceeded）
暴力版本 报超时
C++代码
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int size = T.size();
vector<int> res;
if(size == 0){
return res;
}
for(int i = 0; i < size - 1; i++){
for(int j = i + 1; j < size; j++){
if(j == size - 1 && T[j] <= T[i]){
res.push_back(0);
break;
}
if(T[j] > T[i]){
res.push_back(j - i);
break;
}
}
}
res.push_back(0);
return res;
}
};
递减栈解题思路
- 这道题应该使用递减栈Descending Stack来做，栈里只有递减元素。
- 思路是这样的，我们遍历数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是递减栈了，所以我们取出栈顶元素，那么由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，那么我们直接求出下标差就是二者的距离了，
- 然后继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来了，参见代码如下：
- 可以想一想 [73, 76, 74, 78] 例子。
递减栈版本 AC
C++代码
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int size = T.size();
if(size < 0){
return T;
}
vector<int> res(T.size(), 0);
stack<int> s; // 注意，这个栈存的是索引的位置。
for(int i = 0; i < size; i++){
while(!s.empty() && T[i] > T[s.top()]){
int t = s.top();
s.pop();
res[t] = i - t;
}
s.push(i);
}
return res;
}
};
0206递减栈解题思路
- 这道题应该使用递减栈Descending Stack来做，栈里只有递减元素。
- 初始化这个序列的时候，用res(nums.size(), 0),就是怕后面没有比这个元素大的
- 首先遍历这个序列，不论如何，将序列的索引进行压栈
- 在遍历的时候，如果当前元素大于栈的第一个元素，那么将他们的索引的差值作为 res[t] 的结果
