# Next Greater Element I

`Stack`, `Hash Map`

You are given two arrays **(without duplicates)**`nums1`and`nums2`where`nums1`’s elements are subset of`nums2`. Find all the next greater numbers for`nums1`'s elements in the corresponding places of`nums2`.

The Next Greater Number of a number**x**in`nums1`is the first greater number to its right in`nums2`. If it does not exist, output -1 for this number.

**Example 1:**

```
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
```

**Example 2:**

```
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
```

**Note:**

1. All elements in `nums1` and `nums2` are unique.
2. The length of both `nums1` and `nums2` would not exceed 1000.

## Analysis

Similar idea to [Daily Temperatures](https://aaronice.gitbook.io/lintcode/stack/daily-temperatures) problem.

Keep a **monotonous stack**. 经典问题，单调栈可以轻松解决。

## Solution

Monotonous Stack + HashMap (4 ms, faster than 85.00%)

```java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[nums1.length];

        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                int idx = stack.pop();
                map.put(nums2[idx], nums2[i]);
            }
            stack.push(i);
        }

        for (int j = 0; j < nums1.length; j++) {
            res[j] = map.getOrDefault(nums1[j], -1);
        }

        return res;
    }
}
```