A monotonic stack finds next greater values in one scan

For each value, pop smaller or equal values from a stack of unresolved positions. The remaining top, if present, is the nearest strictly greater value to the left. Then push the current position. Each position is pushed once and popped at most once, so the scan takes O(n) time and O(n) space.