# Leetcode 496 - Next greater element I

Note:

• Monotone stack
• Iterate backwards.
• For each nums2[i], if stack is not empty. It means the last element if monostack is the first element that is greater than nums2[i]. Otherwise, no element is greater than it.
• Use a map to store the greater element, so we don’t need to reiterate monostack again.

Question:

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.

For each 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 -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example:

Code:
Monotone stack

Brute Force O(n^2)