Monotonic Stack
LC #496Easy
Next Greater Element I
Monotonic Stack
AmazonGoogleMetaProblem
For each element in nums1, find the next greater element in nums2.
arraystackhash-map
Constraints
- ›1 ≤ nums1.length ≤ nums2.length ≤ 1000
- ›0 ≤ nums1[i], nums2[i] ≤ 10⁴
- ›All integers in nums2 are unique
- ›nums1 is a subset of nums2
Example
Input
nums1 = [4,1,2], nums2 = [1,3,4,2]Output
[-1,3,-1]Why
4→no greater=-1, 1→next greater in nums2 is 3, 2→no greater=-1