739. 每日温度

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

题目分析

此题要注意的点：如果气温在这之后都不会升高，请在该位置用 0 来代替。
1.暴力
两个for 时间复杂度o(n2)

2.单调栈
时间复杂度o(n),空间换时间
参考链接：739. 每日温度
用单调栈的情况：
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

单调栈里存放的元素是下标，从栈头到栈底是单调递增。
count用下标计算，栈里都是当前没有找到右边比它更大的值的。

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