- For each
nums2[i], if stack is not empty. It means the last element if
monostackis the first element that is greater than nums2[i]. Otherwise, no element is greater than it.
- Use a
mapto store the greater element, so we don’t need to reiterate monostack again.
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
0 <= i < nums1.length, find the index
j such that
nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Brute Force O(n^2)