739。每日温度问题：超出 C++ 时间限制

Question

在执行过程中遇到运行时不佳的情况后，Leetcode 提交已超出时间限制。目前该代码的运行时间为 O(n^2)。如何提高以下问题的时间复杂度？

给定一个整数温度数组代表每日温度，返回一个数组答案，其中答案[i]是在第i天之后您必须等待的天数才能获得较温暖的温度。如果未来没有一天可以这样做，请保留answer[i] == 0。

示例1： 输入：温度 = [73,74,75,71,69,72,76,73] 输出：[1,1,4,2,1,1,0,0]

示例2： 输入：温度 = [30,40,50,60] 输出：[1,1,1,0]

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        
        vector<int> answer;
        int days = 0;

        for (int i = 0; i < temperatures.size(); i++) {
            for (int j = i + 1; j < temperatures.size(); j++) {

                if (temperatures[i] < temperatures[j]) {
                    answer.push_back(j - i);
                    break;
                }
                else if (temperatures[i] >= temperatures[j]) {
                    if (j == temperatures.size() - 1) {
                        answer.push_back(0);
                    }
                }
            }
        }

        answer.push_back(0);
        return answer;
    }
};

Answer 1

这可以通过单调堆栈在线性时间内解决。

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