monotonic_stack.cpp

// Monotonic Stack function to find next greater or next smaller element
vector<int> monotonicStack(const vector<int>& arr, bool findNextGreater = true) {
    int n = arr.size();
    vector<int> res(n, -1); 
    stack<int> st; // Stack to store indices
    
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (findNextGreater ? arr[st.top()] < arr[i] : arr[st.top()] > arr[i])) {
            res[st.top()] = i; // Update result (index of next greater/smaller element)
            st.pop();
        }
        st.push(i);  // Push current index onto the stack
    }

    return res;
}


// Monotonic Stack function to find previous greater or previous smaller element
vector<int> previousMonotonicStack(const vector<int>& arr, bool findPreviousGreater = true) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> st; // Stack to store indices
    
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (findPreviousGreater ? arr[st.top()] <= arr[i] : arr[st.top()] >= arr[i])) 
            st.pop(); 
        
        if (!st.empty()) 
            res[i] = st.top(); // Update result with the index of the previous greater/smaller element

        st.push(i); // Push current index onto the stack
    }

    return res;
}