A stack can answer next-greater queries in one scan

For the next strictly greater value at each array position, keep indices in a stack while their values are waiting for an answer. When a new value is larger, pop indices whose values are smaller and record the new value as their answer. Each index is pushed once and popped once, so the scan takes O(n) time.