visual walkthrough
Next Greater Element I
EasyMonotonic Stack
The simplest monotonic-stack question; learn the template here.
The idea
Every number in nums2 waits for the first bigger number to its right. A stack of waiting numbers solves all of them in one pass: each arriving number settles every smaller number on the stack.
Store the results in a map, then each query is a lookup.
Complexity
| approach | time | space |
|---|---|---|
| Scan right for each query | O(n · m) | O(1) |
| Monotonic stack + map | O(n + m) | O(n) |