Problem: 739. 每日温度

题目描述

思路

若本题目使用暴力法则会超时，故而使用单调栈解决：

1.创建结果数组res，和单调栈stack；
2.循环遍历数组temperatures：

2.1.若当stack不为空同时栈顶所存储的索引对应的气温小于当前的气温，则跟新res中对应位置的值；
2.2.每次向stack中存入每日气温的索引下标

复杂度

时间复杂度:

$O(n)$；其中$n$是数组temperatures的大小

空间复杂度:

$O(n)$

Code

class Solution {
public:
    /**
     * Monotone stack
     *
     * @param temperatures The given temperature array
     * @return vector<int>
     */
    vector<int> dailyTemperatures(vector<int> &temperatures) {
        int n = temperatures.size();
        vector<int> res(n);
        stack<int> stack;
        for (int i = 0; i < n; ++i) {
            while (!stack.empty() && temperatures[stack.top()] < temperatures[i]) {
                int index = stack.top();
                stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
};