Monotonic Stack

One-line trigger: "For each element, find the next / previous element that is greater / smaller."

Keep a stack of indices whose answer is still unknown, in decreasing temperature order. A warmer day resolves several of them at once.

Precompute every next-greater answer for nums2 in one O(n) pass, store it in a map, then answer each nums1 query in O(1).

For each bar, the widest rectangle of that bar's height is bounded by the first strictly smaller bar on each side. A monotonic increasing stack finds both…