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[] nextGreaterElementBruteForce(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int target = nums1[i];
int j = 0;
while (nums2[j] != target) j++; // find target's position in nums2
int nextGreater = -1;
for (int k = j + 1; k < nums2.length; k++) {
if (nums2[k] > target) { nextGreater = nums2[k]; break; }
}
result[i] = nextGreater;
}
return result;
}Time: O(n*m) · Space: O(1) extra beyond the output