[leetcode 739] Daily Temperatures

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.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

 

처음 접근: 포문 돌리기... 당근 시간 초과났다.

 

답 - stack의 사용

스택을 사용하여 t의 인덱스를 저장한다.

언제까지? 현재 t의 온도가 스택의 탑온도보다 클때! => 큰 온도가 처음으로 등장한 것

마지막에 스택에 추가한 온도 < 현재 온도 이면 result[cur_idx] = top_idx-cur_idx하고 스택에서 팝!

 

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