[数据结构与算法]leetcode739. 每日温度

一:题目

二:上码

// class Solution {
// public:
//     vector<int> dailyTemperatures(vector<int>& temperatures) {
//             vector<int> ans(temperatures.size(),0);

//             for (int i = 0; i < temperatures.size(); i++) {

//                 int count = 1;
//                 int flag = 0;

//                 for (int j = i+1; j <temperatures.size(); j++) {
                    
//                     if (temperatures[j] > temperatures[i]) {
//                         flag = 1;
//                         break;
//                     } else {
//                         count++;
//                     }    
//                 }
//                 if(flag == 1) ans[i] = count;
//                 else ans[i] = 0;    
//             }
//             return ans;
//     }
// };



class Solution {
public:

    /**
        思路:1.本题用到单调栈,那么我们来分析一下单调栈;
             2.何时用到单调栈
                当我们要求左边还是右边第一个比其大或者小的元素的位置的时候
             3.怎么用?
                1>:栈当中存的元素
                    存的是元素的下标

                2>:确定何种单调
                    我们从栈顶到栈底的顺序来确定单调性
                     那么本题来说的话 我们是要求出右边第一个比起大的元素位置  
                     那么我们就需要是  单调递增的  
                     当出现元素比其栈顶元素的大的时候  我们就要弹出栈顶元素

                     这时候我们就可以记录了  右边第一个比其大的元素了。 
                     ans[st.top()] = i - st.top();//因为我们是要求的是右边第一个比其大的元素距其相差几个位置

    */


    vector<int> dailyTemperatures(vector<int>& temperatures) {
        
        if(temperatures.size() == 0) return {0};
        
        stack<int> st;
        vector<int> ans(temperatures.size(),0);

        st.push(0);

        for (int i = 1; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {//大于栈顶元素的话  
                                                                            //那么就需要弹出了
                ans[st.top()] = i - st.top();//这时就可以记录我们比栈顶元素大的话  其是相差多少个
                st.pop();
            }   
            st.push(i);  
        }

        return ans;
    }
};