739. Daily Temperatures

문제: https://leetcode.com/problems/daily-temperatures/

Daily Temperatures - LeetCode

 현재 날짜의 기온보다 높은 기온이 나오는 날짜의 차를 각각 구하는 문제다.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        
        vector<int> ans(n, 0);
        stack<int> stk;
        
        for(int i = n - 1; i >= 0; i—){
            int v = temperatures[i];
            
            while(!stk.empty() && temperatures[stk.top()] <= v){
                stk.pop();
            }
            
            if(!stk.empty()){
                int pos = stk.top();
                ans[i] = pos - i;
            } 
            stk.push(i);
        }
        return ans;
    }
};

 첫 번째 솔루션은 stack에다가 현재 값보다 높은 값들만 저장한다.  이러면 처음 높은 값이 stack의 top에 있으며, 없으면 pop을 하면 되므로 답을 구할 수 있다.

 

Time complexity: O(N)

Space complexity: O(N)

 

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        
        vector<int> ans(n, 0);
        int hottest = 0;
        
        for(int i = n - 1; i >= 0; i—){
            int v = temperatures[i];
            if(v >= hottest){
                hottest = v;
                continue;
            }
            
            int days = 1;
            while(temperatures[i + days] <= v){
                days += ans[i + days];
            }
            ans[i] = days;
        }
        return ans;
    }
};

 ans vector에 현 ith 포지션에서 그 보다 높은 온도가 나오는 위치의 차를 가지고있다.  즉, 현재 포지션에서 그 차이만큼 뛰면 해당 온도보다 높은 온도를 extra memory 없이 구할 수 있다.

 

Time complexity: O(N)

Space complexity: O(1)