The next greater element of some element x in an array is the first greater element to its right. Given two arrays nums1 and nums2 (nums1 is a subset of nums2), for each element in nums1, find its next greater element in nums2. If none exists, use -1.
Example 1
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 4 has no greater element to its right in nums2; 1's next greater is 3; 2 has none.
1 <= nums1.length <= nums2.length <= 1000All integers are uniquePrecompute the next-greater-element answer for every number in nums2 once, using a monotonic stack — then look up nums1's answers from that precomputed map.
Don't recompute per-query — that turns an O(n) precomputation into an O(n*m) brute force.
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nextGreater = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int n : nums2) {
while (!stack.isEmpty() && n > stack.peek()) {
nextGreater.put(stack.pop(), n);
}
stack.push(n);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = nextGreater.getOrDefault(nums1[i], -1);
}
return result;
}Time: O(n + m) · Space: O(n)