剑指 Offer II 038. 每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

---

一开始就是暴力的想法

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans;
        int num = 0;
        for (int i = 0; i < temperatures.size(); i++) {
            for (int j = i; j < temperatures.size(); j++) {
                if (temperatures[j] <= temperatures[i])
                    num++;
                else {
                    ans.emplace_back(num);
                    break;
                }
                if (j == temperatures.size() - 1) {
                    ans.emplace_back(0);
                }
            }
            num = 0;
        }
        return ans;
    }
};

运行是超时，后面想着优化用马拉车算法的思想，会跳过小于的数的半径

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        for (int i = temperatures.size()-1; i >=0; i--) {
            for (int j = i; j <temperatures.size(); j++) {
                if (temperatures[j] >temperatures[i]) {
                    ans[i] = j-i;
                    break;
                }
                if (j == temperatures.size() - 1) {
                    ans[i] = 0;
                    break;
                }
                if(ans[j]!=0)
                    j += ans[j] - 1;
            }
        }
        return ans;
    }
};

还是超时，后面朋友告诉我这个题目的标签是栈，终于写过了

class Solution {
public:
    /*马拉车思想做的，超时*/
    /*vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        for (int i = temperatures.size()-1; i >=0; i--) {
            for (int j = i; j <temperatures.size(); j++) {
                if (temperatures[j] >temperatures[i]) {
                    ans[i] = j-i;
                    break;
                }
                if (j == temperatures.size() - 1) {
                    ans[i] = 0;
                    break;
                }
                if(ans[j]!=0)
                    j += ans[j] - 1;
            }
        }
        return ans;
    }*/
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> s;
        vector<int> ans(temperatures.size());
        int j = 0;
        while (j < temperatures.size()) {
            if (s.empty())
                s.emplace(j);
            else {
                int top = s.top();
                while (!s.empty()&&temperatures[top] < temperatures[j]) {
                    ans[top] = j - top;
                    s.pop();
                    top = s.empty()?top:s.top();
                }
                s.push(j);
            }
            j++;
        }
        while (!s.empty()) {
            int top = s.top();
            ans[top] = 0;
            s.pop();
        }
        return ans;
    }
};