496 Next Greater Element I

# 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 numberxin`nums1`is the first greater number to its right in`nums2`. If it does not exist, output -1 for this number.
Example 1:
1
Input:
2
nums1 = [4,1,2],
3
nums2 = [1,3,4,2].
4
5
Output: [-1,3,-1]
6
7
Explanation:
8
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
9
For number 1 in the first array, the next greater number for it in the second array is 3.
10
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Copied!
Example 2:
1
Input:
2
nums1 = [2,4],
3
nums2 = [1,2,3,4].
4
5
Output: [3,-1]
6
7
Explanation:
8
For number 2 in the first array, the next greater number for it in the second array is 3.
9
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Copied!
Note:
1. 1.
All elements in `nums1`and`nums2`are unique.
2. 2.
The length of both`nums1`and`nums2`would not exceed 1000.

# 2. Implementation

1
class Solution {
2
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
3
Map<Integer, Integer> map = new HashMap<>();
4
Stack<Integer> stack = new Stack<>();
5
6
for (int num : nums2) {
7
while (!stack.isEmpty() && stack.peek() < num) {
8
map.put(stack.pop(), num);
9
}
10
stack.push(num);
11
}
12
13
int[] res = new int[nums1.length];
14
for (int i = 0; i < nums1.length; i++) {
15
res[i] = map.getOrDefault(nums1[i], -1);
16
}
17
return res;
18
}
19
}
Copied!