Leetcode - 739. Daily Temperatures

문제

날짜별 온도가 담긴 배열이 주어진다. 각 날짜별로 온도가 처음으로 높아지는 날이 몇일 뒤인지 파악해라.

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

Monotonic Stack 이란?

• increasing
  삽입하려는 값이 stack의 top보다 클때만 push, 삽입하려는 값보다 작은 값은 모두 stack에서 pop.
  배열에서 다음 작은값이 무엇인지 알아낼 수 있음.
• decreasing
  삽입하려는 값이 stack의 top보다 작을 때만 push, 삽입하려는 값보다 큰값은 모두 stack에서 pop.
  배열에서 다음 큰값이 무엇인지 알 수 있음.

해결

brute force(n^2) 해결외에 방법이 잘 떠오르지 않아서,해설을 보니 monotonic stack 기법을 사용하면 된다. temp배열을 하나씩 순회하면서 오늘온도가 스택의 top의 값보다 크면 top에 해당하는 날짜의 값을 계산할 수 있다. 그리고 마지막으로 오늘온도를 stack에 push한다. 이 기법을 잘 숙지하고 있으면 앞으로 유사유형에 사용가능할듯 -> Monotonic Stack

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> stk; // idx, temper
        
        stk.push(make_pair(0, temperatures[0]));
        temperatures[0] = 0;
        for (int i = 1; i < temperatures.size(); i++) {
            while (!stk.empty() && temperatures[i] > stk.top().second) {
                temperatures[stk.top().first] = i - stk.top().first;
                stk.pop();
            }
            stk.push(make_pair(i, temperatures[i]));
            temperatures[i] = 0;
        }
        return temperatures;
    }
    
};

아래는 stack에 index만 저장한 버전. 그런데 아래방법은 공간은 더 적게 사용하지만 속도가 더 느리게 나왔음.

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