LeetCode 739 Daily Temperatures
概述
https://leetcode.com/problems/daily-temperatures/
单调栈
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans(temperatures.size(), 0);
stack<pair<int, int>> s;
for (int i = temperatures.size() - 1; i >= 0; i--) {
while (!s.empty() && s.top().first <= temperatures[i]) {
s.pop();
}
if (!s.empty()) {
ans[i] = s.top().second - i;
}
s.push({temperatures[i], i});
}
return ans;
}
};
利用已计算的值来协助后续计算
当计算第 i 天时,我们首先尝试第 i+1 天(设为 j),如果不行的话,我们下次尝试 ans[j] + j,因为如果 ans[j] 不行的话 下一个可能可行只能是 ans[j] + j(中间的那些值还不如 ans[j])。
最坏时间复杂度 O(n^2)。
实现时要注意给 j 的失败 mark。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans(temperatures.size(), 0);
for (int i = temperatures.size() - 1; i >= 0; i --) {
int j = i + 1;
while (j < temperatures.size() && temperatures[j] <= temperatures[i]) {
if (ans[j] == 0) {
j = temperatures.size(); // mark we cannot find, we cannot use INT_MAX, cause...
break;
};
j += ans[j];
}
if (j != temperatures.size()) ans[i] = j - i;
}
return ans;
}
};