LeetCode739 每日温度

//章节 - 队列和栈    
//三、栈：先入后出的数据结构
//3.每日温度
/*
算法思想：
    审请题意，意思是找一个比当前温度高的最近天数。使用递减栈Descending Stack来做，栈里只有递减元素，思路是这样的，我们遍历数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是递减栈了，所以我们取出栈顶元素，那么由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，那么我们直接求出下标差就是二者的距离了，然后继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来了
*/
//算法实现：
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int t = st.top();   //返回栈顶元素，注意这是返回的是下标
                st.pop();
                res[t] = i - t; //下标差即为距离
            }
            st.push(i); //注意，这是是入栈下标
        }
        return res;
    }
};