The challenge
Return how many days each temperature must wait for a strictly warmer day.
Integer temperatures. Return 0 when no warmer day follows.
Example
[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].
Use the walkthrough below to inspect the input and each state change.
See Daily Temperatures, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 16
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [73,74,75,71,69,72,76,73]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
A warmer day resolves all cooler days waiting at the top.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
n = len(values)
answer, stack = [0] * n, []
for step in range(n):
i = step % n
while stack and values[stack[-1]] < values[i]:
j = stack.pop()
answer[j] = i - j
if step < n: stack.append(i)
return answer
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
vector<int> solve(const vector<int>& values) {
int n = static_cast<int>(values.size());
vector<int> answer(n, 0), stack;
for (int step = 0; step < n; ++step) {
int i = step % n;
while (!stack.empty() && values[stack.back()] < values[i]) {
int j = stack.back(); stack.pop_back();
answer[j] = i - j;
}
if (step < n) stack.push_back(i);
}
return answer;
}