> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/496.-next-greater-element-i-e.md).

# 496. Next Greater Element I (E)

https\://leetcode.com/problems/next-greater-element-i/

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.*

&#x20;

**Example 1:**

```
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
```

**Example 2:**

```
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
```

&#x20;

**Constraints:**

* `1 <= nums1.length <= nums2.length <= 1000`
* `0 <= nums1[i], nums2[i] <= 104`
* All integers in `nums1` and `nums2` are **unique**.
* All the integers of `nums1` also appear in `nums2`.

&#x20;

**Follow up:** Could you find an `O(nums1.length + nums2.length)` solution?

### Solution:

单调栈：

```
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        int[] result = new int[nums1.length];
        Map<Integer, Integer> map= new HashMap<Integer, Integer>();
        for(int i = 0;i< nums1.length; i++)
        {
            map.put(nums1[i], i);
        }
        
        int[] nums2Result = new int[nums2.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i = nums2.length-1; i >= 0; i--)
        {
            while(!stack.empty() && stack.peek() <= nums2[i])
            {
                stack.pop();
            }
            nums2Result[i] = stack.empty() ? -1: stack.peek();
            if(map.containsKey(nums2[i]))
            {
                result[map.get(nums2[i])] = nums2Result[i];
            }
            stack.push(nums2[i]);
        }
        return result;
        
    }
}
```