739. Daily Temperatures

Posted on Edited on In

739. Daily Temperatures

Description

Difficulty: Medium

Related Topics: Array, Stack, Monotonic Stack

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:

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

Example 2:

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

Example 3:

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

Constraints:

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

Hints/Notes

Solution

Language: C++

Left to right:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> stk;
        int n = temperatures.size();
        vector<int> res(n, 0);
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && temperatures[i] > stk.top().second) {
                auto [idx, _] = stk.top();
                stk.pop();
                res[idx] = i - idx;
            }
            stk.emplace(i, temperatures[i]);
        }
        return res;
    }
};

Right to left:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> warmer;
        int size = temperatures.size();
        vector<int> res(size, 0);
        for (int i = size - 1; i >= 0; i--) {
            while (!warmer.empty() && warmer.top().first <= temperatures[i]) {
                warmer.pop();
            }
            res[i] = warmer.empty() ? 0 : warmer.top().second - i;
            warmer.push({temperatures[i], i});
        }
        return res;
    }
};