今天开始学习单调栈部分，自己是真正的初次接触单调栈这个概念，因此需要打好基础。

739.每日温度

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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

思路：

1.一开始看到这道题肯定会想到双重for循环的暴力解法，而双重for循环无非也是相当于暂时记录当前的一个元素，然后遍历该元素之后的所有元素找第一个比它大的。此时我们就可以想到用单调栈来存储我们已经遍历过的元素，使得只用一遍循环就可以达到我们想要的效果。

2.我们将遍历过的元素下标存储进单调栈中，从栈头到栈尾按照递增的顺序来存储（因为实际每次比较时都是先和栈头的元素比较，我们要找的是右边第一个比自己大的元素），如果当前元素小于等于栈顶元素那么我们将其入栈，如果大于那么我们就将两个元素的下标进行相减得到一个结果，并开始循环以上操作直到栈顶元素比当前元素大的情况或者栈为空（最后一定别忘记在while循环结束后要将当前元素入栈！）

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(), 0);
        stack<int> st;
        st.push(0);

        for(int i = 1; i < temperatures.size(); i++){
            if(temperatures[i] <= temperatures[st.top()]){
                st.push(i);
            }
            else{
                while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }

        return result;
    }
};

启发：

1.作为初次接触单调栈的题目，让我认识到何所谓单调栈——栈内存储的元素一定按照某种规律进行单调，由此比较适合用于求当前元素左边或者右边第一个比自己大、小之类的问题。

2.本题选择用单调栈存储元素的下标而非元素值，主要还是因为我们要求的是右边第一个比自己大的元素到自己的距离，而距离实际上就是两个元素的下标，因此直接存储下标最为方便，存储值只是方便比较大小但不好找到对应下标计算距离。