力扣 hot100 Day67

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

//抄的
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> answer(n, 0);stack<int> stk; // 存储的是天数索引for (int i = 0; i < n; ++i) {// 当栈不为空且当前温度大于栈顶那天的温度时while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {int prev_day = stk.top();stk.pop();answer[prev_day] = i - prev_day; // 计算天数差}stk.push(i); // 压入当前天数}return answer;}
};

stk是一个单调栈，索引对应温度值栈底至栈顶递增，具体逻辑如下

当栈为空或者当前天数温度小于栈顶值时，说明当前温度还不够高，不能解决任何等待中的天数的需求，所以直接推入当前天数；当当前天数大于栈顶值时，说明正是栈顶天数想要的，此时pop，保存数据，并循环判断，最后同样要压入当前天数。

可以这样理解，压栈是为了保存过去的数据，后续找到想找到值才让其出栈，通过维持一个单调栈，动态记录结果。