#include <iostream>
#include <vector>
#include <stack>
void printVector(std::vector<int> const &v) {
for (auto const &n: v) {
std::cout << n << " ";
}
}
std::vector<int> number_of_days_needed_to_wait_to_get_warmer(std::vector<int>& temperatures) {
int size = temperatures.size();
std::vector<int> result(size, 0);
std::stack<int> stk;
for (int i = 0; i < size; i++) {
while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
int index = stk.top();
stk.pop();
result[index] = i - index;
}
stk.push(i);
}
return result;
}
int main() {
std::vector<int> temperatures = {82, 84, 81, 58, 85, 89, 75, 71};
// 82 -> 84 = 1
// 84 -> 81 -> 58 -> 85 = 3
// 81 -> 58 -> 85 = 2
// 58 -> 85 = 1
// 85 -> 89 = 1
// 89 -> 75 -> 71 = 0
// 75 -> 71 = 0
std::vector<int> result = number_of_days_needed_to_wait_to_get_warmer(temperatures);
printVector(result);
}
/*
run:
1 3 2 1 1 0 0 0
*/
