749.Daily Temperatures¶
Tags: Medium
Stack
Array
Links: https://leetcode.com/problems/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]
.
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = T.size();
vector<int> res(n, 0);
stack<int> s; s.push(0);
for (int i = 1; i < n; ++i) {
if (s.empty()) s.push(i);
else {
while (!s.empty() && T[i] > T[s.top()]) {
res[s.top()] = i - s.top(); s.pop();
}
s.push(i);
}
}
return res;
}
};
单调栈的模板题,注意一下,是记录**经过几天**超过当前值,而不是第一个大于当前值的位置。