【栈 - LeetCode】739.每日温度

739. 每日温度 - 力扣（LeetCode）

题解

暴力+技巧

官网给的一个暴力遍历的方式，技巧点在于，温度的最大值是 100， 因此里面的 for 循环可以通过控制最大是到 100 来降低时间复杂度。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int>ans(n), next(101, INT_MAX);for(int i = n - 1; i >= 0; i --){int index = INT_MAX;for(int t = temperatures[i] + 1; t <= 100; t ++){index = min(index, next[t]);}if(index != INT_MAX){ans[i] = index - i;}next[temperatures[i]] = i;}return ans;}
};

单调栈

栈中存储还没有被找到的 满足条件的 第 x 天。

如果是递增序列，栈中始终就一个元素，不断移入移出。

如果是非递增，则一直入栈，找到第一个大于栈顶的，再依次出栈判断。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);stack<int> s;for (int i = 0; i < n; i++) {while (!s.empty() && temperatures[i] > temperatures[s.top()]) {int index = s.top();ans[index] = i - index;s.pop();}s.push(i);}return ans;}
};