[LeetCode] 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/?envType=daily-question&envId=2024-01-31

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Daily Temperatures

문제 유형 : 스택, 모노토닉 스택

문제 난이도 : Medium

 

 

문제

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.

 

정수 배열 array가 주어진다. 일일 온도를 나타낸다.

answer[i]가 i번째날 이후로 더 따뜻한 날까지 며칠을 기다려야 하는지
를 만족하는 배열 answer를 반환하시오.

더 따뜻한 날이 없으면, answer[i] = 0으로 하시오.

 

 

풀이

스택에(온도, 날짜)형태로 저장하여 배열의 뒤쪽부터 탐색한다.

처음 날짜는 무조건 0이므로, 스택에는 (temperature[n-1], n-1)을 넣고, n-2부터 0까지 배열을 순회한다.

 

스택에 값이 있는동안, 또는 스택에 더 큰 값이 나올 때까지 스택에서 값을 pop한다.

만약 스택에 값이 없다면, i번째날 이후로 더 따뜻한 날이 없다는 뜻이다.

값이 있다면, 그 날의 온도가 i번째날 이후로 따뜻한 첫 날이다. answer[i]에 저장시킨다.

스택에 (temperature[i], i)를 넣고 계속 진행한다.

 

코드

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        const int n = temperatures.size();
        vector<int> answer (n, 0);
        stack<vector<int>> st;
        st.push({temperatures[n-1], n-1});
        for(int i = n-2; i >= 0; i--) {
            while(!st.empty() && temperatures[i] >= st.top()[0]) st.pop();

            if(!st.empty()) answer[i] = st.top()[1] - i;

            st.push({temperatures[i], i});
        }

        return answer;
    }
};