Monotonic Stack

Key Signals & Indicators

• Need to search for the next greater or smaller element in one direction
• Range bounds calculation, or histograms values comparisons
• Avoids nested O(n^2) loops by pruning states linearly in O(n)

// C++ Next Greater Element Monotonic Stack Template
#include <vector>
#include <stack>

std::vector<int> nextGreaterElement(const std::vector<int>& arr) {
    std::vector<int> result(arr.size(), -1);
    std::stack<int> s; // Stack holds indices
    
    for (int i = 0; i < arr.size(); ++i) {
        // Maintain monotonic decreasing stack
        while (!s.empty() && arr[i] > arr[s.top()]) {
            result[s.top()] = arr[i]; // Next greater element found
            s.pop();
        }
        s.push(i);
    }
    return result;
}