0、 Preface

This blog is to buckle 739. Daily temperature Problem solving , The problem is not difficult , I little interesting , But in coding There was a little problem in the process ！

Github The relevant content of this blog can be Click here to To view the ！

1、 Title Description

2、 Their thinking

2.1 Method 1~ Violent solution

2.1.1 Ideas

This method starts from the first number in the target array , Compare it with the following elements , Just find the subscript difference of the first number larger than him .

This method is easy to implement , But the problem is that my following program will show timeout in some cases ~
So we need to change the way ！

2.1.2 Program code

class Solution {
    
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
    
        vector<int> ans(temperatures.size());
        for(int i=0;i<temperatures.size()-1;i++)
        {
    
            for(int j=i+1;j<temperatures.size();j++)
            {
    
                if(temperatures[j]>temperatures[i])
                {
    
                    ans[i] = j-i;
                    break;
                }
            }
        }
        return ans;
    }
};

2.2 Method 2 ~ Using monotone stack

2.2.1 Ideas

Forward traversal of the target array , For each of these elements temperatures[i], If the stack st It's empty , Will directly i Into the stack , If the stack is not empty , Compare stack top elements st.top() Corresponding temperature temperatures[st.top()] And current temperature temperatures[i] Size , If temperatures[i] > temperatures[st.top()], Set the waiting days corresponding to the top element of the stack to i - st.top(), And push the top element out of the stack . Repeat the above operation until the stack is empty or the temperature corresponding to the top element of the stack is less than or equal to the current temperature .

In fact, at the beginning of this topic, I thought of using stack , But what I want is to keep the temperature value in the stack , Instead of saving the subscript corresponding to the temperature value , This led me to start coding Something's wrong ~
But always come back and say , This question has a somewhat eye opening effect , That's interesting ~

2.2.2 Program code

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