LeetCode Hot 100 P739 Daily Temperatures

---

Timeline

Timeline

2026-03-18

init

Monotonic stack

---

Problem:

P739 Daily Temperatures

https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

Monotonic stack, where elements in the stack always remain monotonically decreasing

#include <vector>
#include <stack>

using std::vector;
using std::stack;

class Solution {
    public:
        vector<int> dailyTemperatures(vector<int> &temperatures)
        {
                int i, n = temperatures.size();
                vector<int> res(n, 0);
                stack<int> stk; // Monotonic stack, monotonically decreasing

                for (i = 0; i < n; i++) {
                        while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                                res[stk.top()] = i - stk.top();
                                stk.pop();
                        }

                        stk.push(i);
                }

                while (!stk.empty()) {
                        res[stk.top()] = 0;
                        stk.pop();
                }
                res[n - 1] = 0;

                return res;
        }
};

#include <cstdio>
int main()
{
        Solution S;
        vector<int> temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
        vector<int> res;

        res = S.dailyTemperatures(temperatures);

        for (int val : res)
                std::printf("%d ", val);

        printf("\n");
}