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;}
};