The Monotonic Stack: Next Greater Element

Waiting for something bigger

For each day's temperature, find the next warmer day. Checking forward from each day is O(n²). Instead keep a stack of days still waiting; their temperatures go down from bottom to top (monotonic). When a warmer day arrives, it answers every cooler day waiting on top.

Think of it like this: People waiting for someone taller to walk in. When a tall person arrives, everyone shorter who was waiting gets their answer and leaves.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    vector<int> temps = {30, 28, 32, 31, 29, 35};
    vector<int> answer(temps.size(), -1);
    stack<int> waiting;                       // indexes still waiting
    for (int i = 0; i < (int)temps.size(); i++) {
        while (!waiting.empty() && temps[waiting.top()] < temps[i]) {
            answer[waiting.top()] = temps[i];
            waiting.pop();
        }
        waiting.push(i);
    }
    for (int a : answer) cout << a << ' ';
    cout << endl;
    return 0;
}

Output

32 32 35 35 35 -1 

Every index is pushed once and popped at most once: O(n).

Remember: “Next bigger” or “previous smaller” in the problem? Think monotonic stack.