decreasing stack O(n) time O(n) space
维护一个单调递减栈，栈里存下标，每次遇到更高的温度，对栈里的下标对应的结果进行更新后弹出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[s.top()] < temperatures[i]) {
res[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
return res;
}
};
|
从后往前维护一个单调递减栈，栈里存下标，每次判断当前下标和栈里第一个符合要求的下标的间距即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n);
stack<int> s;
for (int i = n - 1; i >= 0; --i) {
while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
s.pop();
}
res[i] = s.empty() ? 0 : (s.top() - i);
s.push(i);
}
return res;
}
};
|