Stack monotonic

A monotonic stack stores unresolved candidates in sorted order. First identify the exact relation: next greater commonly scans left to right while maintaining a decreasing stack, whereas previous greater can answer directly from a decreasing stack before pushing. Store indices when distances or values from the original array are needed. For each current value, pop stack entries that can no longer be the relevant candidate under the chosen comparison. After pops, the top is the nearest valid candidate if one exists; record the answer, then push the current index. The comparison must handle duplicates deliberately: use < versus <= depending on whether equal values count as greater or smaller. Although the code has nested-looking loops, every index is pushed once and popped once, so time is O(n) and stack space is O(n). Explain why a popped dominated item cannot serve any future element.