739. Daily Temperature

1) Problem Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

2) First Try

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

The above code exeeds time limit: time complexity of the code is O(n^2), where n is the size of T

3) Second Try

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> days = vector<int>(T.size(),0);
        priority_queue<pair<int,int>> pq;
        
        pq.push({-T[0],0});
        for(int i=1; i<T.size(); i++){
            //update "days" if the temp on ith day is warmer than on nth day in pq
            while(!pq.empty() && T[i]>-pq.top().first){
                int n = pq.top().second; pq.pop();
                days[n] = i-n;
            }
            pq.push({-T[i],i});
        }
        return days;
    }
};

This code passes the test, but the time complexity is still not linear time and the runtime is only about 5% faster than other submissions(which basically means that it is not efficient at all).

4) Third Try

Then I found a much simpler way.

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

It’s actually doing the same thing as in the second try, but instead a stack was used in the third try. It’s much faster because it only saves indices(integers). For every temperature on ith day, check if it’s warmer than any days on the stack(from the top). If T[i]>T[stack.top], pop the index out of the stack and count the days. Keep comparing temperatures until T[i] is smaller than the T[stack.top] (or stack is empty). It is ensured that for the rest of the former days(as index j on the stack), T[j]>T[i] because T[j]>T[stack.top]. (If T[j]<T[stack.top], j should have been already popped out of the stack).

It’s a bit frustrating how I couldn’t come up with this simple answer in the first place.