Monotonic Stacks

A monotonic stack keeps candidate indices in an ordered sequence while preserving the ordinary LIFO interface. When a new element makes older candidates useless, they are removed permanently. This turns problems that appear to require a scan for every index into linear-time algorithms. We will solve next strictly greater and next strictly smaller elements, compute stock spans, and find the largest rectangle in a histogram. The runnable program includes all four so their different inequality choices can be compared directly.

Prerequisites: Stacks, Arrays and Vectors, and amortized analysis from vector growth.

Build the idea

1. 1. Next greater means unresolved work. Scan a from left to right and keep indices whose next greater value has not yet appeared. For each i, while a[stack.back()] < a[i], pop index j and record i as its next greater index. Why is i the first such index? j remained unresolved through every earlier processed position, so none was strictly greater. The stack's values are nonincreasing from bottom to top after each insertion. Equal values remain because “strictly greater” excludes equality. Any indices still on the stack at the end have answer 0, meaning none exists.
2. 2. Trace next greater and smaller. For [2,1,5,6,2,3], processing 5 resolves indices 2 and 1, processing 6 resolves index 3, and processing the final 3 resolves index 5. Next-greater indices are [3,3,4,0,6,0]. Reverse the comparison to > for next strictly smaller: the pending values become nondecreasing, and the answers are [2,0,5,5,0,0]. This lesson returns indices, not values; that lets a caller compute distances or retrieve the actual answer value. Returning 0 is unambiguous with 1-based indexing.
3. 3. Stock span uses a previous barrier. The span at i counts consecutive ending positions with value at most a[i], including i itself. Maintain a strictly decreasing stack of earlier values by popping while a[top] ≤ a[i]. The remaining top is the nearest earlier value strictly greater than a[i], which blocks the span. If its index is p, span[i]=i−p; if no barrier remains, use p=0. For [2,1,5,6,2,3], spans are [1,1,3,4,1,2]. The equality rule differs from next greater because equal earlier prices belong inside the span and must be removed as barriers.
4. 4. A histogram rectangle is limited by its shortest bar. To find maximum area under nonnegative heights, keep indices in nondecreasing height order. When height h[i] is smaller than h[top], the popped bar j can no longer extend right beyond i−1. After popping j, the new top p is a left boundary; the candidate width is i−p−1, or i−1 if empty. Area is h[j] times width. Equal heights may remain with this strict-pop convention: some duplicate candidates get shorter widths, but a surviving equal-height representative eventually receives the full span. Do not mix formulas from a different tie convention without proving them.
5. 5. Flush pending histogram bars. Append a conceptual sentinel of height -1 after the last bar. Because real heights are nonnegative, it forces every pending bar to be evaluated. For [2,1,5,6,2,3], height 5 spans positions 3..4 with area 10, which is maximal. The sentinel is never stored, so the input vector requires no extra mutation. Use long long for area: even moderate heights multiplied by a long width may overflow int. The example rejects negative histogram heights, which would not match the intended geometric model.
6. 6. Prove linear time by charging work to indices. A while loop may pop many entries in one iteration, but each index is pushed once and popped at most once in each pass. There are at most n pushes and n pops, so the whole pass is O(n), not O(n²). This is amortized analysis. The stack is not binary search and does not merely speed up the inner scan; it proves discarded candidates can never be needed again. Before adapting the pattern, state what candidates mean, which direction values must be ordered, and whether equality counts as greater/smaller or as a barrier.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>nextIndex(const vector<long long>&a,bool greater){
    int n=static_cast<int>(a.size())-1;
    vector<int>ans(n+1,0),st;
    // Stack indices are unresolved; each leaves at its first qualifying value.
    for(int i=1;i<=n;++i){
        while(!st.empty()&&(greater?a[st.back()]<a[i]:a[st.back()]>a[i])){
            ans[st.back()]=i; // This first qualifying value resolves the index.
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}
vector<int>stockSpans(const vector<long long>&a){
    int n=static_cast<int>(a.size())-1;
    vector<int>span(n+1),st;
    for(int i=1;i<=n;++i){
        while(!st.empty()&&a[st.back()]<=a[i]){
            st.pop_back();
        }
        // The remaining top is the nearest earlier strictly greater barrier.
        span[i]=i-(st.empty()?0:st.back());
        st.push_back(i);
    }
    return span;
}
long long largestRectangle(const vector<long long>&h){
    int n=static_cast<int>(h.size())-1;
    vector<int>st;
    long long best=0;
    for(int i=1;i<=n+1;++i){
        long long current=(i==n+1?-1:h[i]);
        while(!st.empty()&&h[st.back()]>current){
            int j=st.back();
            st.pop_back();
            int left=st.empty()?0:st.back();
            long long width=i-left-1; // Exclude both blocking boundaries.
            best=max(best,h[j]*width);
        }
        if(i<=n){
            st.push_back(i); // Do not store the sentinel index.
        }
    }
    return best;
}
void print(const vector<int>&a){
    for(int i=1;i<static_cast<int>(a.size());++i){
        if(i>1){
            cout<<' ';
        }
        cout<<a[i];
    }
    cout<<'\n';
}
int main(){
    int n;
    if(!(cin>>n)||n<0){
        return 0;
    }
    vector<long long>a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]<0||a[i]>1000000000LL){
            return 0;
        }
    }
    print(nextIndex(a,true));
    print(nextIndex(a,false));
    print(stockSpans(a));
    cout<<largestRectangle(a)<<'\n';
}

Complexity analysis

Each of the four passes is O(n) time because every index enters and leaves its stack at most once. Four linear passes still give O(n) total time. Input, answer arrays, and the largest pending stack require O(n) space; each stack can hold all n indices on a monotone or equal sequence. Histogram area uses 64-bit multiplication, and the stated height bound keeps area within 64 bits for int-sized n.

Example input and output

Read n ≥ 0 and n heights in [0,10^9]. Output next-greater indices, next-smaller indices, stock spans, then largest rectangle area. Vertices are not involved; sequence positions are 1-based. For n=0, output three blank lines and area 0.

Input

6
2 1 5 6 2 3

Output

3 3 4 0 6 0
2 0 5 5 0 0
1 1 3 4 1 2
10

The first two lines give next strictly greater and next strictly smaller indices, with 0 for absent answers. The third gives stock spans. The largest histogram rectangle covers bars 3 and 4 with minimum height 5 and width 2, so area is 10.

Practical applications

Use monotonic stacks for nearest greater/smaller neighbors, stock spans, histogram rectangles, visible-building problems, and Cartesian-tree construction. Nearest-smaller boundaries also help count subarrays where each element is minimum; duplicate attribution there requires one strict and one non-strict boundary to avoid double counting.

Check your understanding

Why can a monotonic stack with an inner while loop still run in O(n)?

Put it into practice

Change the next-greater routine to return the next greater-or-equal index, then test [4,4,4].