C++ ] leetCode 739 - Daily Temperatures

 

 

 

리트코드 739번 문제

 

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

 

Example 1:

• Input: temperatures = [73,74,75,71,69,72,76,73]
• Output: [1,1,4,2,1,1,0,0]

 

 

Example 2:

• Input: temperatures = [30,40,50,60]
• Output: [1,1,1,0]

 

Example 3:

• Input: temperatures = [30,60,90]
• Output: [1,1,0]

 

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

 

이중 루프를 사용해서 각 인덱스에 대해 나머지 배열을 순회하면 시간초과로 못푸는 문제이고, 대신 stack 자료구조를 사용해 풀 수 있다.

 

아직 더 따뜻한 온도를 만나지 못한 온도의 인덱스는 스택에 저장해두고 배열을 순회하면서 스택에 있는 인덱스 온도보다 새로 등장한 온도가 더 따뜻한 경우 스택에서 인덱스를 꺼내 현재의 인덱스와 차이를 answer 배열에 채워 넣으면 된다.

 

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        stack<int> s;

        for(int i = 0; i < n; i++) {
            while(!s.empty() && (temperatures[s.top()] < temperatures[i])) {
                answer[s.top()] = i - s.top();
                s.pop();                
            }
            s.push(i);
        }

        return answer;
    }
};