跳转至

739 每日温度

https://leetcode.cn/problems/daily-temperatures/description/

找出左/右边第一个比栈顶元素小 -> 单调递增栈

找出左/右边第一个比栈顶元素大 -> 单调递减栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> stk;
        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++){
            // 单调递减栈,弹出说明新元素i是第一个比栈顶元素大的元素
            while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){
                // 题目问的是几天后
                ans[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};

复杂度分析

时间复杂度:O(n),其中 n 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。

空间复杂度:O(n),其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。