【LeetCode】739.每日温度

题目描述

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

输入输出示例及数据范围

思路：单调栈

我们当然可以使用暴力求解的方式解决这道题，但是更优的做法是使用单调栈。具体来说，单调栈当中存储的是原数组的下标，并满足栈顶元素（下标）对应到原数组当中的值在栈中是最大的。

我们从头开始对 temperatures 数组进行遍历，并在遍历的过程中维护整个单调栈。对于第i个元素，我们首先不断地取栈顶的下标prev对应的元素temperatures[prev]与temperatures[i]比较大小，如果前者比后者小，那么说明prev 这个下标对应的这一天找到了与它最近且问题比它高的那一天，prev这一天的答案就是i - prev。不断地比较直至栈清空或是temperatures[prev]不比temperatures[i]小，此时将i入栈即可。

C++ 实现

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n, 0);stack<int> st;for(int i=0; i<n; i++) {while(!st.empty() && temperatures[st.top()] < temperatures[i]) {int prev = st.top();ans[prev] = i - prev;st.pop();}st.push(i);}return ans;}
};