# 496    Next Greater Element I

## 496. [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/description/)

## 1. Question

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.

## 2. Implementation

**思路**: 题目已经说明nums1是nums2的子集，所以可以对nums2进行遍历，维护一个单调递减stack, 当栈顶的数小于当前nums2的数时，则nums2是栈顶数的Next Greater Element。同时通过一个HashMap记录每个元素的Next Greater Element即可

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

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

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

## 3. Time & Space Complexity

时间和空间复杂度都为O(n), n为nums2里的元素个数