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].
暴力解法(复杂度为O(n^2),编译器报超时了):
vector<int> dailyTemperatures(vector<int>& temperatures) {
int i, j;
int n = temperatures.size();
vector<int> res(n);
for (i = 0; i < n-1; i++) { //从0到n-2
for (j = i+1; j < n; j++) { //j从i之后找
if (temperatures[j] > temperatures[i]) { //找到一个就跳出
res[i] = j-i;
break;
}
}
if (j == n) res[i] = 0; //若找不到
}
res[i] = 0; //最后一位必为0
return res;
}
别人的思路(用栈,时间O(n)(近似),空间O(n)):
上面的暴力思路是用i遍历数组,然后对每个i向后找.
现在思路是用i遍历数组,然后对每个i向前(在栈里)找.已经找到的元素直接出栈(或许这就是O(n)?),挺奇妙的.
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> s; //序号栈
vector<int> res(temperatures.size()); //结果,长度与temps一样,初始元素全为0
for (int i = 0; i < temperatures.size(); i++) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) { //若找到第一个比栈顶温度大的
res[s.top()] = i - s.top(); //i与栈顶的序号之差
s.pop(); //出栈
}
s.push(i); //若没找到比栈顶大的,先把i入栈,成为新栈顶
}
return res;
}
