739. Daily Temperature

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

Problem

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].

Solution

1. Naive approach using hash map

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> indice(71, -1);
        vector<int> days_wait(T.size());
        for (int i = T.size() - 1; i >= 0; --i) {
            int min_index = INT_MAX;
            for (int j = T[i] + 1; j <= 100; ++j) {
                if (indice[j - 30] < 0) continue;
                min_index = min(min_index, indice[j - 30]);
            }
            indice[T[i] - 30] = i;
            if (min_index != INT_MAX) days_wait[i] = min_index - i;
        }
        return days_wait;
    }
};

2. Optimized using stack

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<pair<int,int>> temp2index;
        vector<int> days_wait(T.size());
        for (int i = T.size() - 1; i >= 0; --i) {
            while (!temp2index.empty() && temp2index.top().first <= T[i]) temp2index.pop();
            if (!temp2index.empty()) days_wait[i] = temp2index.top().second - i;
            temp2index.push({T[i], i});
        }
        return days_wait;
    }
};

• #stack

• #hash